In 1994, Kranakis et al. published a conjecture about the minimum link-length of every rectilinear covering path for the \(k\)-dimensional grid \(P(n,k) := \{0,1, \dots, n-1\} \times \{0,1, \dots, n-1\} \times \cdots \times \{0,1, \dots, n-1\}\). In this paper we consider the general, NP-complete, Line-Cover problem, where the edges are not required to be axis-parallel, … Read more
Based on extensive computational evidence (hundreds of thousands of randomly generated problems) the second author conjectured that $\bar{\kappa}(\zeta)=1$, which is a factor of $\sqrt{2n}$ better than that has been proved, and which would yield an $O(\sqrt{n})$ iteration full-Newton step infeasible interior-point algorithm. In this paper we present an example showing that $\bar{\kappa}(\zeta)$ is in the … Read more
We present a new computer system, called GraPHedron, which uses a polyhedral approach to help the user to discover optimal conjectures in graph theory. We define what should be optimal conjectures and propose a formal framework allowing to identify them. Here, graphs with n nodes are viewed as points in the Euclidian space, whose coordinates … Read more