On the exact complexity of Hamiltonian Cycle and q-Colouring in disk graphs

DOI10.1007/978-3-319-57586-5_31MaRDI QIDQ5283382zbMATH OpenOpenAlexFDO

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

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) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Fine-grained complexity of coloring unit disks and balls
• Fast exact algorithms for Hamiltonicity in claw-free graphs
• Fine-grained complexity of coloring unit disks and balls
• The complexity of colouring circle graphs (extended abstract)

Cites work

• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• Cut and count and representative sets on branch decompositions
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Hamilton Paths in Grid Graphs
• On coloring unit disk graphs
• Parameterized algorithms
• Separators for sphere-packings and nearest neighbor graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Cited in

(4)

• 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
• Recognition and proper coloring of unit segment intersection graphs

This page was built for publication: On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283382)