Proper interval graphs and the guard problem

DOI10.1016/S0012-365X(96)00307-XzbMath0877.05034MaRDI QIDQ1363667

Chiuyuan Chen, Chin-Chen Chang, Gerard Jennhwa Chang

Publication date: 10 August 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian cyclesvisibilityHamiltonicityHamiltonian pathsinterval graphsHamiltonian-connectedspiral polygonsguard problemstick-intersection graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (11)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Hamiltonian paths, unit-interval complexes, and determinantal facet ideals ⋮ Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ Backup 2-center on interval graphs ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ Minimal classes of graphs of unbounded clique-width ⋮ General-demand disjoint path covers in a graph with faulty elements ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• On the compatibility between a graph and a simple order
• Recognizing visibility graphs of spiral polygons
• Covering the edges with consecutive sets
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Proper interval graphs and the guard problem