Deferred-query—An efficient approach for problems on interval and circular-arc graphs

DOI10.1007/3-540-57155-8_250MaRDI QIDQ5060115zbMATH OpenOpenAlexFDO

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

Publication date 18 January 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57155-8_250

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 some problems on interval graphs
• Paths in interval graphs and circular arc graphs
• Solving the all-pair shortest path query problem on interval and circular-arc graphs
• Linear time algorithms on circular-arc graphs
• Paired domination on interval and circular-arc graphs

Cites work

• A linear-time algorithm for a special case of disjoint set union
• An Efficient Test for Circular-Arc Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Deferred-query: An efficient approach for some problems on interval graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear algorithm for domatic number problem on interval graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Linear time algorithms on circular-arc graphs
• Minimum node disjoint path covering for circular-arc graphs
• On the domatic number of interval graphs
• Preserving order in a forest in less than logarithmic time and linear space
• Stability in circular arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Domatic Number Problem in Interval Graphs
• The edge Hamiltonian path problem is NP-complete
• The NP-completeness column: an ongoing guide
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Towards a theory of domination in graphs

Cited in

(5)

• A matrix characterization of interval and proper interval graphs
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• A polynomial algorithm for the k-cluster problem on the interval graphs
• Deferred-query: An efficient approach for some problems on interval graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

This page was built for publication: Deferred-query—An efficient approach for problems on interval and circular-arc graphs

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