Proper interval graphs and the guard problem

DOI10.1016/S0012-365X(96)00307-XzbMATH Open0877.05034MaRDI QIDQ1363667FDOQ1363667

Gerard Jennhwa Chang, Chiuyuan Chen, Chin-Chen 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)

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A linear-time algorithm for proper interval graph recognition
• Recognizing visibility graphs of spiral polygons
• Covering the edges with consecutive sets

Cited In (13)

• 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
• Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
• A simple algorithm to find Hamiltonian cycles in proper 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
• Canonical antichains of unit interval and bipartite permutation graphs
• Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
• Complexity of Hamiltonian cycle reconfiguration
• General-demand disjoint path covers in a graph with faulty elements

   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 👍 👎

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)