Polynomial time recognition of unit circular-arc graphs

DOI10.1016/J.JALGOR.2004.08.003MaRDI QIDQ5468870zbMATH OpenOpenAlexFDO

Authors Guillermo Durán, Agustín Gravano, R. M. McConnell, Jeremy P. Spinrad, Alan C. Tucker

Publication date 28 April 2006

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10533/177861

zbMATH Keywords

Circular-arc graphsGraph algorithmsPolynomial recognitionProper circular-arc graphsUnit circular-arc graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Recognizing circle graphs in polynomial time
• Linear-time recognition of circular-arc graphs
• A simpler linear-time recognition of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Polynomial time recognition of uniform cocircuit graphs
• scientific article; zbMATH DE number 437537
• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs

Cited in

(20)

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Linear-time recognition of circular-arc graphs
• Completing colored graphs to meet a target property
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• NP-completeness results for edge modification problems
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Partial Characterizations of Circular-Arc Graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Partial characterizations of circular-arc graphs
• scientific article; zbMATH DE number 6829367 (Why is no real title available?)
• Circular-arc bigraphs and its subclasses
• scientific article; zbMATH DE number 2230201 (Why is no real title available?)
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Recognizing hyperelliptic graphs in polynomial time
• Partial characterizations of circle graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Obstacle numbers of graphs

This page was built for publication: Polynomial time recognition of unit circular-arc graphs

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