Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)

DOI10.1007/3-540-61576-8_71zbMATH1543.68274MaRDI QIDQ6567668FDOQ6567668

Authors Chiuyuan Chen, Chin-Chen Chang

Publication date 5 July 2024

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Covering the edges with consecutive sets
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Hamilton Paths in Grid Graphs
• Incidence matrices and interval graphs
• Recognizing visibility graphs of spiral polygons
• Reducibility among combinatorial problems
• 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

(1)

• Semi-proper interval graphs

This page was built for publication: Connected proper interval graphs and the guard problem in spiral polygons (extended abstract)

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