• COVERING PATHS IN HYPERCUBES: CONJECTURE ABOUT LINK LENGTH BOUNDED FROM BELOW

MARCO RIPÀ*

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 c1.5 for the lower order terms.


Keywords


graph theory, topology, combinatorics, segment, connectivity, outside the box, upper bound, lower bound, point.

Full Text:

PDF


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
© 2010-2019 International Journal of Mathematical Archive (IJMA)
Copyright Agreement & Authorship Responsibility
Web Counter