Paper Info
Title
A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
Abstract
A circular-arc model $ {\mathcal {M}} =(C,\mathcal{A})$ is a circle Ctogether with a collection $\mathcal{A}$ of arcs of C. If no arc is contained in any other then $\mathcal{M}$ is a proper circular-arc model, and if some point of Cis not covered by any arc then ${\mathcal{M}}$ is an interval model. A (proper) (interval) circular-arc graph is the intersection graph of a (proper) (interval) 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. For the isomorphism problem, there exists a polynomial time algorithm for the general case, and a linear time algorithm for interval graphs. In this work we develop a linear time algorithm for the isomorphism problem in proper circular-arc graphs, based on uniquely encoding a proper circular-arc model. Our method relies on results about uniqueness of certain PCA models, developed by Deng, Hell and Huang in [6]. The algorithm is easy to code and uses only basic tools available in almost every programming language.
Year
DOI
Venue
2008
10.1007/978-3-540-69903-3_32
SWAT
Keywords
Field
DocType
simple linear time algorithm,interval model,isomorphism problem,interval graph,proper circular-arc graphs,circular-arc model,proper circular-arc model,certain pca model,proper circular-arc graph,linear time algorithm,circular-arc graph,linear time recognition algorithm,programming language,linear time
Uniqueness,Discrete mathematics,Indifference graph,Combinatorics,Arc (geometry),Graph isomorphism,Existential quantification,Algorithm,Intersection graph,Isomorphism,Time complexity,Mathematics
Conference
Volume
ISSN
Citations 
5124
0302-9743
8
PageRank 
References 
Authors
0.51
16
3
Name
Order
Citations
PageRank
Min Chih Lin125921.22
Francisco J. Soulignac210110.56
Jayme L. Szwarcfiter354645.97