Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs

DOI10.1007/11917496_26MaRDI QIDQ3522966zbMATH OpenOpenAlexFDO

Authors Haim Kaplan, Yahav Nussbaum

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_26

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Linear-time recognition of circular-arc graphs
• Polynomial time recognition of unit circular-arc graphs
• Proper Helly Circular-Arc Graphs

Cited in

(16)

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Fully dynamic recognition of proper circular-arc graphs
• A simple certifying algorithm for 3-edge-connectivity
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Proper Helly Circular-Arc Graphs
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Certifying algorithms
• From a Circular-Arc Model to a Proper Circular-Arc Model
• Powers of cycles, powers of paths, and distance graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Polynomial time recognition of unit circular-arc graphs
• Linear-time recognition of Helly circular-arc models and graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• The clique operator on circular-arc graphs

This page was built for publication: Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs

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