INVESTIGADORES
LIN Min Chih
congresos y reuniones científicas
Título:
Characterizations and linear time recognition of Helly circular-arc graphs
Autor/es:
MIN CHIH LIN; JAYME L. SZWARCFITER
Lugar:
Taipei, Taiwan
Reunión:
Conferencia; COCOON'06 (12th Annual International Computing and Combinatorics Conference); 2006
Institución organizadora:
Academia Sinica, Taiwan
Resumen:
A circular-arc model
is a circle C together with a collection
of arcs of C. If
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 algorithm 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(n3).
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.