Finding Hamiltonian circuits in interval graphs
From MaRDI portal
The problem of deciding whether a graph has a Hamiltonian circuit has been shown NP-complete on many restricted classes of graphs. This paper adds to the classes of graphs for which a polynomial time algorithm for the Hamiltonian circuit problem is known. A linear time algorithm for the problem in interval graphs is developed.
Recommendations
- Hamiltonian circuits in interval graph generalizations
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
- Paths in interval graphs and circular arc graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Powers of Hamiltonian paths in interval graphs
Cites work
- A Characterization of Comparability Graphs and of Interval Graphs
- Finding Hamiltonian circuits in proper interval graphs
- Hamilton Paths in Grid Graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Incidence matrices with the consecutive 1’s property
- Representation of a finite graph by a set of intervals on the real line
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The edge Hamiltonian path problem is NP-complete
- The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
Cited in
(89)- A linear time recognition algorithm for proper interval graphs
- Finding the minimum bandwidth of an interval graph
- Hamiltonian circuits in interval graph generalizations
- On the domatic number of interval graphs
- On finding the minimum bandwidth of interval graphs
- Searching for \(f\)-Hamiltonian circuits
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Generalized vertex covering in interval graphs
- Hamiltonian cycle is polynomial on cocomparability graphs
- Paths in interval graphs and circular arc graphs
- Linear algorithm for domatic number problem on interval graphs
- 1-tough cocomparability graphs are hamiltonian
- Proper interval graphs and the guard problem
- Tractabilities and intractabilities on geometric intersection graphs
- Jump number maximization for proper interval graphs and series-parallel graphs
- Achromatic number is NP-complete for cographs and interval graphs
- Toughness, hamiltonicity and split graphs
- HAMILTONian circuits in chordal bipartite graphs
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- The Steiner cycle and path cover problem on interval graphs
- A simple linear time algorithm to solve the MIST problem on interval graphs
- Mim-width. I. Induced path problems
- The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
- The longest cycle problem is polynomial on interval graphs
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Disjoint path covers joining prescribed source and sink sets in interval graphs
- Computing and counting longest paths on circular-arc graphs in polynomial time
- The harmonious coloring problem is NP-complete for interval and permutation graphs
- Toughness in graphs -- a survey
- A note on longest paths in circular arc graphs
- Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
- Complexity of Steiner tree in split graphs -- dichotomy results
- Computing and counting longest paths on circular-arc graphs in polynomial time
- Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem
- A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
- Hamiltonicity in Split Graphs - A Dichotomy
- On computing longest paths in small graph classes
- The Longest Path Problem Is Polynomial on Interval Graphs
- 10-tough chordal graphs are Hamiltonian (extended abstract)
- 10-tough chordal graphs are Hamiltonian
- scientific article; zbMATH DE number 140140 (Why is no real title available?)
- Powers of Hamiltonian paths in interval graphs
- Subgraph isomorphism in graph classes
- Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
- scientific article; zbMATH DE number 4117862 (Why is no real title available?)
- A new Hamilton circle algorithm of the closure that is complete graph
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Deferred-query—An efficient approach for problems on interval and circular-arc graphs
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
- On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
- Simple Geometrical Intersection Graphs
- Chvátal's \(t_{0}\)-tough conjecture
- scientific article; zbMATH DE number 2230266 (Why is no real title available?)
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Total domination in interval graphs
- Parameterized complexity of multicut in weighted trees
- Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
- 2-Trees: Structural insights and the study of Hamiltonian paths
- Path eccentricity of graphs
- Complexity of maximum cut on interval graphs
- The longest path problem has a polynomial solution on interval graphs
- Hamiltonian properties of locally connected graphs with bounded vertex degree
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)
- Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
- A closer look at Hamiltonicity and domination through the lens of diameter and convexity
- On the structure of Hamiltonian graphs with small independence number
- The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
- Tree-layout based graph classes: proper chordal graphs
- Domination and cut problems on chordal graphs with bounded leafage
- Hamiltonian path in permutation graphs
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- Computing Hamiltonian paths with partial order restrictions
- On the structure of Hamiltonian graphs with small independence number
- Some properties of \(k\)-trees
- Complexity of maximum cut on interval graphs
- Triangles improve 0.878 approximation for Maxcut
- Efficient reduction for path problems on circular-arc graphs
- Cyclability in graph classes
- Toughness and Hamiltonicity in k-trees
- 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
- New sequential and parallel algorithms for interval graph recognition
- Finding Hamiltonian circuits in quasi-adjoint graphs
- Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
This page was built for publication: Finding Hamiltonian circuits in interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1066674)
