Deferred-query—An efficient approach for problems on interval and circular-arc graphs
From MaRDI portal
Publication:5060115
DOI10.1007/3-540-57155-8_250zbMath1504.68156OpenAlexW1717014977MaRDI QIDQ5060115
Jenn-Liang Liaw, Sheng-Lung Peng, 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
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 (4)
A matrix characterization of interval and proper interval graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Domination, independent domination, and duality in strongly chordal graphs
- Linear algorithm for optimal path cover problem on interval graphs
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- A linear-time algorithm for a special case of disjoint set union
- Finding Hamiltonian circuits in interval graphs
- Hamiltonian circuits in interval graph generalizations
- On the domatic number of interval graphs
- The edge Hamiltonian path problem is NP-complete
- Linear time algorithms on circular-arc graphs
- Preserving order in a forest in less than logarithmic time and linear space
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Minimum node disjoint path covering for circular-arc graphs
- Linear algorithm for domatic number problem on interval graphs
- The NP-completeness column: an ongoing guide
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Stability in circular arc graphs
- An Efficient Test for Circular-Arc Graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Towards a theory of domination in graphs
- Deferred-query: An efficient approach for some problems on interval graphs
- The Domatic Number Problem in Interval Graphs
This page was built for publication: Deferred-query—An efficient approach for problems on interval and circular-arc graphs
