TY - GEN

T1 - Direct and certifying recognition of normal helly circular-arc graphs in linear time

AU - Cao, Yixin

PY - 2014/1/1

Y1 - 2014/1/1

N2 - A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. [Discrete Appl. Math. 2013] presented the first recognition algorithm for this graph class by characterizing circular-arc graphs that are not in it. They posed as an open problem to design a direct recognition algorithm, which is resolved by the current paper. When the input is not a normal Helly circular-arc graph, our algorithm finds in linear time a minimal forbidden induced subgraph. Grippo and Safe [arXiv:1402.2641] recently reported the forbidden induced subgraphs characterization of normal Helly circular-arc graphs. The correctness proof of our algorithm provides, as a byproduct, an alternative proof to this characterization.

AB - A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. [Discrete Appl. Math. 2013] presented the first recognition algorithm for this graph class by characterizing circular-arc graphs that are not in it. They posed as an open problem to design a direct recognition algorithm, which is resolved by the current paper. When the input is not a normal Helly circular-arc graph, our algorithm finds in linear time a minimal forbidden induced subgraph. Grippo and Safe [arXiv:1402.2641] recently reported the forbidden induced subgraphs characterization of normal Helly circular-arc graphs. The correctness proof of our algorithm provides, as a byproduct, an alternative proof to this characterization.

UR - http://www.scopus.com/inward/record.url?scp=84903558234&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08016-1_2

DO - 10.1007/978-3-319-08016-1_2

M3 - Conference article published in proceeding or book

SN - 9783319080154

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings

PB - Springer Verlag

T2 - 8th International Frontiers of Algorithmics Workshop, FAW 2014

Y2 - 28 June 2014 through 30 June 2014

ER -