Proper interval graphs and the guard problem

DOI10.1016/S0012-365X(96)00307-XMaRDI QIDQ1363667zbMATH OpenFDO

Authors Chiuyuan Chen, Chin-Chen Chang, Gerard Jennhwa Chang

Publication date 10 August 1997

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

interval graphsHamiltonian cyclesvisibilityHamiltonicityHamiltonian-connectedHamiltonian pathsspiral polygonsguard problemstick-intersection graphs

Mathematics Subject Classification ID

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

Recommendations

• Paths in interval graphs and circular arc graphs
• Hamiltonian circuits in interval graph generalizations
• Finding Hamiltonian circuits in interval graphs
• The eternal dominating set problem for proper interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• A linear-time algorithm for proper interval graph recognition
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Covering the edges with consecutive sets
• Finding Hamiltonian circuits in proper interval graphs
• Graph theory
• Incidence matrices and interval graphs
• On the compatibility between a graph and a simple order
• Recognizing visibility graphs of spiral polygons
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(13)

• General-demand disjoint path covers in a graph with faulty elements
• Algorithms for finding disjoint path covers in unit interval graphs
• Backup 2-center on interval graphs
• Proper interval graph extention problems of the complements of trees
• Minimal classes of graphs of unbounded clique-width
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Characterization of interval graphs that are unpaired 2-disjoint path coverable
• Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
• Semi-proper interval graphs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Canonical antichains of unit interval and bipartite permutation graphs
• Complexity of Hamiltonian cycle reconfiguration

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363667)