A Simpler Linear-Time Recognition of Circular-Arc Graphs

DOI10.1007/11785293_7zbMath1142.68622OpenAlexW201513316MaRDI QIDQ5757898

Haim Kaplan, Yahav Nussbaum

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11785293_7

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Some results on the limits of thought ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Coloring fuzzy circular interval graphs ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Proper Helly Circular-Arc Graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ The clique operator on circular-arc graphs ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes

This page was built for publication: A Simpler Linear-Time Recognition of Circular-Arc Graphs