Polynomial time recognition of unit circular-arc graphs
From MaRDI portal
Publication:5468870
DOI10.1016/j.jalgor.2004.08.003zbMath1093.68071OpenAlexW2138933466MaRDI QIDQ5468870
Agustín Gravano, Guillermo Durán, Jeremy P. Spinrad, Ross M. McConnell, 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
Graph algorithmsCircular-arc graphsPolynomial recognitionProper circular-arc graphsUnit circular-arc graphs
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (13)
Circular‐Arc Bigraphs and Its Subclasses ⋮ Partial Characterizations of Circular-Arc Graphs ⋮ Partial characterizations of circle graphs ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Obstacle numbers of graphs ⋮ NP-completeness results for edge modification problems ⋮ Completing colored graphs to meet a target property ⋮ Unnamed Item ⋮ Partial characterizations of circular-arc graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey
This page was built for publication: Polynomial time recognition of unit circular-arc graphs