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.
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||8th International Frontiers of Algorithmics Workshop, FAW 2014|
|Period||28/06/14 → 30/06/14|
- Theoretical Computer Science
- Computer Science(all)