Deferred-query: An efficient approach for some problems on interval graphs

DOI<1::AID-NET1>3.0.CO;2-C 10.1002/(SICI)1097-0037(199908)34:1<1::AID-NET1>3.0.CO;2-CzbMath0959.90058OpenAlexW1987647154MaRDI QIDQ4262690

Sheng-Lung Peng, Jenn-Liang Liaw, Maw-Shang Chang

Publication date: 22 September 1999

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>3.0.co;2-c

zbMATH Keywords

Hamiltonian circuitmaximum matchinggraph algorithmsHamiltonian pathinterval graphsdomatic partitionoptimal path cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Cyclability in graph classes, Deferred-query—An efficient approach for problems on interval and circular-arc graphs, Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs, The longest path problem has a polynomial solution on interval graphs, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, The Longest Path Problem is Polynomial on Cocomparability Graphs, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, The Steiner cycle and path cover problem on interval graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Domination, independent domination, and duality in strongly chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Unnamed Item
• Unnamed Item