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

DOI10.1002/(SICI)1097-0037(199908)34:1%3C1::AID-NET1%3E3.0.CO;2-CMaRDI QIDQ4262690zbMATH OpenOpenAlexFDO

Authors 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%3C1::aid-net1%3E3.0.co;2-c

zbMATH Keywords

domatic partitiongraph algorithmsHamiltonian circuitHamiltonian pathinterval graphsmaximum matchingoptimal path cover

Mathematics Subject Classification ID

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

Recommendations

• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• scientific article; zbMATH DE number 123468
• Some parallel algorithms on interval graphs
• scientific article; zbMATH DE number 3892606
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• scientific article; zbMATH DE number 4068905
• Efficient enumeration of non-isomorphic interval graphs
• On the parameterized complexity of multiple-interval graph problems
• An efficient algorithm to solve \(L(0,1)\)-labelling problem on interval graphs
• Succinct data structures for families of interval graphs

Cites work

• Domination, independent domination, and duality in strongly chordal graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(12)

• 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
• The longest path problem is polynomial on cocomparability graphs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval 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
• Cyclability in graph classes

This page was built for publication: Deferred-query: An efficient approach for some problems on interval graphs

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