Finding Hamiltonian circuits in interval graphs

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

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

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?)
A Characterization of Comparability Graphs and of Interval Graphs
Finding Hamiltonian circuits in proper interval graphs
Hamilton Paths in Grid Graphs
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 Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
The Planar Hamiltonian Circuit Problem is NP-Complete
The edge Hamiltonian path problem is NP-complete

Cited in

(77)

Path eccentricity of graphs
The Steiner tree in $K_{1,r}$-free split graphs -- a dichotomy
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Hamiltonicity in Split Graphs - A Dichotomy
Recognition and isomorphism of proper $H $-graphs for unicyclic $H$ in \textit{FPT}-time
U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
$\mathcal{U}$-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)
Hamiltonian cycles in 7-tough $(P_3 \cup 2P_1)$-free graphs
2-Trees: Structural insights and the study of Hamiltonian paths
Disjoint path covers joining prescribed source and sink sets in interval graphs
The longest cycle problem is polynomial on interval graphs
A closer look at Hamiltonicity and domination through the lens of diameter and convexity
Kernelization of graph Hamiltonicity: proper $H$-graphs
A simple linear time algorithm to solve the MIST problem on interval graphs
scientific article; zbMATH DE number 140140 (Why is no real title available?)
A new Hamilton circle algorithm of the closure that is complete graph
The Longest Path Problem Is Polynomial on Interval Graphs
Complexity of maximum cut on interval graphs
Achromatic number is NP-complete for cographs and interval graphs
Finding Hamiltonian circuits in quasi-adjoint graphs
scientific article; zbMATH DE number 4117862 (Why is no real title available?)
scientific article; zbMATH DE number 2230266 (Why is no real title available?)
HAMILTONian circuits in chordal bipartite graphs
10-tough chordal graphs are Hamiltonian
New sequential and parallel algorithms for interval graph recognition
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
A note on longest paths in circular arc graphs
1-tough cocomparability graphs are hamiltonian
Deferred-query—An efficient approach for problems on interval and circular-arc graphs
Full cycle extendability of locally connected $K_{1,4}$-restricted graphs
The Steiner cycle and path cover problem on interval graphs
Toughness in graphs -- a survey
Searching for $f$-Hamiltonian circuits
Toughness, hamiltonicity and split graphs
Hamiltonian cycle is polynomial on cocomparability graphs
Mim-width. I. Induced path problems
Computing and counting longest paths on circular-arc graphs in polynomial time
Simple Geometrical Intersection Graphs
Linear algorithm for domatic number problem on interval graphs
Some properties of $k$-trees
A linear time recognition algorithm for proper interval graphs
scientific article; zbMATH DE number 7651188 (Why is no real title available?)
Efficient reduction for path problems on circular-arc graphs
Jump number maximization for proper interval graphs and series-parallel graphs
Tractabilities and intractabilities on geometric intersection graphs
Generalized vertex covering in interval graphs
Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
On finding the minimum bandwidth of interval graphs
Linear algorithm for optimal path cover problem on interval graphs
Complexity of Steiner tree in split graphs -- dichotomy results
Subgraph isomorphism in graph classes
Computing and counting longest paths on circular-arc graphs in polynomial time
Cyclability in graph classes
Paths in interval graphs and circular arc graphs
Parameterized complexity of multicut in weighted trees
Hamiltonian properties of locally connected graphs with bounded vertex degree
Chvátal's $t_{0}$-tough conjecture
Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem
A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
10-tough chordal graphs are Hamiltonian (extended abstract)
On the domatic number of interval graphs
A polynomial solution to the $k$-fixed-endpoint path cover problem on proper interval graphs
Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
The harmonious coloring problem is NP-complete for interval and permutation graphs
Finding the minimum bandwidth of an interval graph
On toughness and Hamiltonicity of $2K_{2}$-free graphs
Total domination in interval graphs
Toughness threshold for the existence of 2-walks in $K_{4}$-minor-free graphs
On computing longest paths in small graph classes
A simple algorithm to find Hamiltonian cycles in proper interval graphs
The longest path problem has a polynomial solution on interval graphs
Toughness and Hamiltonicity in $k$-trees
Hamiltonian circuits in interval graph generalizations

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)