Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
verfasst von : Sándor Kisfaludi-Bak, Tom C. van der Zanden
Erschienen in: Algorithms and Complexity
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study the exact complexity of the Hamiltonian Cycle and the q-Colouring problem in disk graphs. We show that the Hamiltonian Cycle problem can be solved in \(2^{O(\sqrt{n})}\) on n-vertex disk graphs where the ratio of the largest and smallest disk radius is O(1). We also show that this is optimal: assuming the Exponential Time Hypothesis, there is no \(2^{o(\sqrt{n})}\)-time algorithm for Hamiltonian Cycle, even on unit disk graphs. We give analogous results for graph colouring: under the Exponential Time Hypothesis, for any fixed q, q-Colouring does not admit a \(2^{o(\sqrt{n})}\)-time algorithm, even when restricted to unit disk graphs, and it is solvable in \(2^{O(\sqrt{n})}\)-time on disk graphs.