Finding Hamiltonian circuits in interval graphs

DOI10.1016/0020-0190(85)90050-XzbMath0578.68053MaRDI QIDQ1066674

J. Mark Keil

Publication date: 1985

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

zbMATH Keywords

polynomial time algorithmlinear time algorithminterval graphs

Mathematics Subject Classification ID

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

Cyclability in graph classes ⋮ Finding the minimum bandwidth of an interval graph ⋮ Hamiltonian circuits in interval graph generalizations ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ 10-tough chordal graphs are Hamiltonian (extended abstract) ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Unnamed Item ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ 10-tough chordal graphs are Hamiltonian ⋮ On the domatic number of interval graphs ⋮ Toughness and Hamiltonicity in \(k\)-trees ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Toughness, hamiltonicity and split graphs ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Mim-width. I. Induced path problems ⋮ HAMILTONian circuits in chordal bipartite graphs ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs ⋮ Parameterized complexity of multicut in weighted trees ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Path eccentricity of graphs ⋮ Unnamed Item ⋮ Complexity of maximum cut on interval graphs ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Linear algorithm for optimal path cover problem 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 ⋮ Subgraph isomorphism in graph classes ⋮ New sequential and parallel algorithms for interval graph recognition ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ The longest cycle problem is polynomial on interval graphs ⋮ The harmonious coloring problem is NP-complete for interval and permutation graphs ⋮ On finding the minimum bandwidth of interval graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Finding Hamiltonian circuits in quasi-adjoint graphs ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Generalized vertex covering in interval graphs ⋮ Hamiltonian cycle is polynomial on cocomparability graphs ⋮ Toughness threshold for the existence of 2-walks in \(K_{4}\)-minor-free graphs ⋮ Total domination in interval graphs ⋮ On Toughness and Hamiltonicity of 2K₂‐Free Graphs ⋮ Paths in interval graphs and circular arc graphs ⋮ Some properties of \(k\)-trees ⋮ Toughness in graphs -- a survey ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Unnamed Item ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Simple Geometrical Intersection Graphs ⋮ A note on longest paths in circular arc graphs ⋮ Linear algorithm for domatic number problem on interval graphs ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ Unnamed Item ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Achromatic number is NP-complete for cographs and interval graphs ⋮ The Steiner cycle and path cover problem on interval graphs ⋮ Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time ⋮ Chvátal’s t 0-Tough Conjecture ⋮ Efficient reduction for path problems on circular-arc graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding Hamiltonian circuits in proper interval graphs
• The edge Hamiltonian path problem is NP-complete
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Representation of a finite graph by a set of intervals on the real line
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton Paths in Grid Graphs
• Incidence matrices with the consecutive 1’s property
• A Characterization of Comparability Graphs and of Interval Graphs