Finding Hamiltonian circuits in interval graphs

DOI10.1016/0020-0190(85)90050-XMaRDI QIDQ1066674zbMATH OpenFDO

Authors J. Mark Keil

Publication date 1985

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

Full work available at URL https://doi.org/10.1016/0020-0190(85)90050-X

zbMATH Keywords

interval graphslinear time algorithmpolynomial time algorithm

Mathematics Subject Classification ID

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

(86)

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

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)