Finding Hamiltonian circuits in proper interval graphs
From MaRDI portal
Publication:1050117
DOI10.1016/0020-0190(83)90078-9zbMath0512.68046OpenAlexW2077143033MaRDI QIDQ1050117
Publication date: 1983
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(83)90078-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)
Related Items
Algorithms for finding disjoint path covers in unit interval graphs ⋮ Hamiltonian circuits in interval graph generalizations ⋮ Some parallel algorithms on interval graphs ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Unnamed Item ⋮ Proper interval graphs and the guard problem ⋮ On the domatic number of interval graphs ⋮ Hamiltonian paths, unit-interval complexes, and determinantal facet ideals ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ HAMILTONian circuits in chordal bipartite graphs ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Path eccentricity of graphs ⋮ Frobenius methods in combinatorics ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Finding Hamiltonian circuits in quasi-adjoint graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Paths in interval graphs and circular arc graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Intersection graphs of non-crossing paths ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ Tropical paths in vertex-colored graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Mathematical properties on the hyperbolicity of interval graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs ⋮ Finding Hamiltonian circuits in interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The edge Hamiltonian path problem is NP-complete
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Minimum node disjoint path covering for circular-arc graphs
- An Efficient Test for Circular-Arc Graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- Algorithms on circular-arc graphs
- Coloring a Family of Circular Arcs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- On the complexity of computing the measure of ∪[a i ,b i ]
- Algorithms for a maximum clique and a maximum independent set of a circle graph
This page was built for publication: Finding Hamiltonian circuits in proper interval graphs
