INVESTIGADORES
SOULIGNAC Francisco Juan
artículos
Título:
On cliques of Helly circular-arc graphs
Autor/es:
MIN CHIH LIN; ROSS M. MCCONNELL; FRANCISCO J. SOULIGNAC; JAYME L. SZWARCFITER
Revista:
Electronic Notes in Discrete Mathematics
Editorial:
Elsevier
Referencias:
Lugar: Amsterdam; Año: 2008 vol. 30 p. 117 - 122
ISSN:
1571-0653
Resumen:
A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique. A Helly circular-arc graph is proper if it has a Helly model where no arc is a subset of another. In this paper, we show that the clique intersection graphs of Helly circular-arc graphs are related to the proper Helly circular-arc graphs. This yields the first polynomial (linear) time recognition algorithm for the clique graphs of Helly circular-arc graphs. Next, we develop an O(n) time algorithm to obtain a clique model of Helly model, improving the previous O(n^2) bound. This gives a linear-time algorithm to find a proper Helly model for the clique graph of a Helly circular-arc graph. As an application, we find a maximum weighted clique of a Helly circular-arc graph in linear time.
