Linear-Time Recognition of Helly Circular-Arc Models and Graphs |
| |
Authors: | Benson?L?Joeris Email author" target="_blank">Min?Chih?LinEmail author Ross?M?McConnell Jeremy?P?Spinrad Jayme?L?Szwarcfiter |
| |
Affiliation: | (1) Department of Computer Science, Colorado State University, Fort Collins, CO 80523-1873, USA |
| |
Abstract: | A circular-arc model ℳ is a circle C together with a collection
A\mathcal{A}
of arcs of C. If
A\mathcal{A}
satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph
of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention
in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses.
However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n
3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by
forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing
graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of
it, within this same bound. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|