Paper Info
Title
Characterizations and linear time recognition of helly circular-arc graphs
Abstract
A circular-arc model $(C, \cal A)$ is a circle C together with a collection $\cal A$ of arcs of C. If $\cal A$ satisfies the Helly Property then $(C, \cal A)$ 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.
Year
DOI
Venue
2006
10.1007/11809678_10
COCOON
Keywords
Field
DocType
characterizations lead,helly property,helly circular-arc graph,helly circular-arc model,circular-arc graph,linear time recognition algorithm,circular-arc model,general class,best recognition algorithm,intersection graph,satisfiability,linear time,col
Graph,Discrete mathematics,Combinatorics,Arc (geometry),Interval graph,Helly's theorem,Intersection graph,Negative - answer,Recognition algorithm,Time complexity,Mathematics
Conference
Volume
ISSN
ISBN
4112
0302-9743
3-540-36925-2
Citations 
PageRank 
References 
11
0.73
6
Authors
2
Name
Order
Citations
PageRank
Min Chih Lin125921.22
Jayme L. Szwarcfiter254645.97