Hamiltonian circuits in interval graph generalizations

DOI10.1016/0020-0190(86)90135-3zbMath0627.68056OpenAlexW2028363955MaRDI QIDQ1092669

Maurizio A. Bonuccelli, Alan A. Bertossi

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90135-3

zbMATH Keywords

Hamiltonian circuitchordal graphsNP-completeintersection graphsundirected path graphsdouble interval graphsrectangle 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)

Related Items (34)

Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ HAMILTONian circuits in chordal bipartite graphs ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ Edge deletion to tree-like graph classes ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ On 3-degree 4-chordal graphs ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Subgraph isomorphism in graph classes ⋮ Dominating sets in perfect graphs ⋮ The Hamiltonian properties of supergrid graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Paths in interval graphs and circular arc graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ A note on the Hamiltonian circuit problem on directed path graphs ⋮ A linear time recognition algorithm for proper interval graphs ⋮ The Hamiltonian circuit problem for circle graphs is NP-complete ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ On the recognition of search trees generated by BFS and DFS ⋮ Revising Johnson's table for the 21st century ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• The edge Hamiltonian path problem is NP-complete
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On double and multiple interval graphs
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• Extremal Values of the Interval Number of a Graph
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton Paths in Grid Graphs
• Characterizing circular-arc graphs
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide

This page was built for publication: Hamiltonian circuits in interval graph generalizations