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
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
