Paper Info
Title
On cliques of Helly Circular-arc Graphs
Abstract
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(n2) 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.
Year
DOI
Venue
2008
10.1016/j.endm.2008.01.020
Electronic Notes in Discrete Mathematics
Keywords
DocType
Volume
algorithms,Helly circular-arc graphs,proper Helly circular-arc graphs,clique graphs,maximum weight cliques
Journal
30
ISSN
Citations 
PageRank 
1571-0653
6
0.52
References 
Authors
6
4
Name
Order
Citations
PageRank
Min Chih Lin125921.22
R McConnell282566.28
Francisco J. Soulignac310110.56
Jayme L. Szwarcfiter454645.97