Open AccessLinear-time recognition of circular-arc graphs
Author(s) -
R.M. McConnell
Publication year - 2001
Publication title -
proceedings 42nd ieee symposium on foundations of computer science
Language(s) - English
Resource type - Conference proceedings
pISSN - 1552-5244
DOI - 10.1109/sfcs.2001.959913
Subject(s) - computing and processing , communication, networking and broadcast technologies
A graph G is a circular-arc graph if it is the intersection graph of a set of arcs on a circle. That is, there is one arc for each vertex of G, and two vertices are adjacent in G if the corresponding arcs intersect. We give a linear time bound for recognizing this class of graphs. When G is a member of the class, the algorithm gives a certificate in the form of a set of arcs that realize it.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom