کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949883 | 1364262 | 2017 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection](/preview/png/4949883.png)
A normal Helly circular-arc graph is the intersection graph of a set of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. (2013) characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used them to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as a certificate. Our approach yields also a considerably simpler algorithm for the certifying recognition of proper Helly circular-arc graphs, a subclass of normal Helly circular-arc graphs.
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 67-83