Email this article FPT-Algorithm for Computing the Width of a Simplex Given by a Convex Hull
- Authors: Veselov S.I.1, Gribanov D.V.1, Malyshev D.S.2
-
Affiliations:
- Institute of Information Technologies, Mathematics, and Mechanics
- Faculty of Informatics, Mathematics and Computer Science
- Issue: Vol 43, No 1 (2019)
- Pages: 1-11
- Section: Article
- URL: https://journals.rcsi.science/0278-6419/article/view/176271
- DOI: https://doi.org/10.3103/S0278641919010084
- ID: 176271
Cite item
Open Access
Access granted
Subscription Access
Abstract
The problem of computing the width of simplices generated by the convex hull of their integer vertices is considered. An FPT algorithm, in which the parameter is the maximum absolute value of the rank minors of the matrix consisting from the simplex vertices, is presented.
About the authors
S. I. Veselov
Institute of Information Technologies, Mathematics, and Mechanics
Author for correspondence.
Email: sergey.veselov@itmm.unn.ru
Russian Federation, Nizhny Novgorod, 603950
D. V. Gribanov
Institute of Information Technologies, Mathematics, and Mechanics
Author for correspondence.
Email: dimitry.gribanov@gmail.com
Russian Federation, Nizhny Novgorod, 603950
D. S. Malyshev
Faculty of Informatics, Mathematics and Computer Science
Author for correspondence.
Email: dsmalyshev@rambler.ru
Russian Federation, Nizhny Novgorod, 603155
Supplementary files
