An optimum (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals

DOI10.1016/0020-0190(90)90025-SMaRDI QIDQ915465zbMATH OpenFDO

Authors Glenn K. Manacher, Terrance A. Mankus, Carol Joan Smith

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90025-S

zbMATH Keywords

Hamiltonian circuitHamiltonian pathinterval graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding Hamiltonian circuits in interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Hamiltonian circuits in interval graph generalizations
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• A simple linear expected time algorithm for finding a Hamilton path

Cites work

• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Minimum node disjoint path covering for circular-arc graphs
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• 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

Cited in

(19)

• An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs
• 1-tough cocomparability graphs are hamiltonian
• Toughness, hamiltonicity and split graphs
• The Steiner cycle and path cover problem on interval graphs
• The longest cycle problem is polynomial 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
• 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
• An efficient parallel algorithm for scheduling interval ordered tasks
• Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)
• Simple linear time recognition of unit interval graphs
• Hamiltonian path in permutation graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Cyclability in graph classes
• Linear algorithm for optimal path cover problem on interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs

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

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