An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
From MaRDI portal
Publication:915465
DOI10.1016/0020-0190(90)90025-SzbMath0702.68069MaRDI QIDQ915465
Glenn K. Manacher, Terrance A. Mankus, Carol Joan Smith
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (17)
Cyclability in graph classes ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ Toughness, hamiltonicity and split graphs ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Linear algorithm for optimal path cover problem on interval graphs ⋮ An efficient parallel algorithm for scheduling interval ordered tasks ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Simple linear time recognition of unit interval graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ An optimal algorithm for solving the searchlight guarding problem on weighted interval 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
- Unnamed Item
- Finding Hamiltonian circuits in proper interval graphs
- Finding Hamiltonian circuits in interval 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
- On the complexity of computing the measure of ∪[a i ,b i ]
This page was built for publication: An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
