• COVERING PATHS IN HYPERCUBES: CONJECTURE ABOUT LINK LENGTH BOUNDED FROM BELOW
Abstract
In 1994 Kranakis et al. published a conjecture about the minimal length of a rectilinear (polygonal) covering path in a k-dimensional n × ... × n points grid. In this paper we consider the general Line-Cover problem, where the line-segments are not required to be axis-parallel, showing that, given n = 3 < k, the known lower bound is not greater than the upper bound of the original Kranakis’ conjecture only if exists a multiplicative constant c ≥ 1.5 for the lower order terms.
Keywords
Full Text:
PDFThis work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
© 2010-2022 International Journal of Mathematical Archive (IJMA) Copyright Agreement & Authorship Responsibility |