The Hamiltonian circuit problem for circle graphs is NP-complete
From MaRDI portal
Publication:1823687
DOI10.1016/0020-0190(89)90059-8zbMath0681.68062OpenAlexW2052982152MaRDI QIDQ1823687
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90059-8
Related Items (20)
The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Embedding ray intersection graphs and global curve simplification ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole ⋮ Lower bounds on the mim-width of some graph classes ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Parameterized domination in circle graphs ⋮ The Hamiltonian properties of supergrid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Paths in interval graphs and circular arc graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Unnamed Item ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Revising Johnson's table for the 21st century ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm
Cites Work
This page was built for publication: The Hamiltonian circuit problem for circle graphs is NP-complete
