On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs

DOI10.1007/978-3-319-57586-5_31zbMath1486.68134OpenAlexW2607365952MaRDI QIDQ5283382

Tom C. van der Zanden, Sándor Kisfaludi-Bak

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

Computing list homomorphisms in geometric intersection graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

Cites Work

• On coloring unit disk graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Separators for sphere-packings and nearest neighbor graphs
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Cut and Count and representative sets on branch decompositions
• Hamilton Paths in Grid Graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Unnamed Item

This page was built for publication: On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs