Premium
Polynomial time algorithms on circular‐arc overlap graphs
Author(s) -
Kashiwabara Toshinobu,
Masuda Sumio,
Nakajima Kazuo,
Fujisawa Toshio
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210205
Subject(s) - combinatorics , arc (geometry) , mathematics , circle graph , graph , time complexity , split graph , algorithm , discrete mathematics , chordal graph , 1 planar graph , line graph , pathwidth , geometry
Let S be a family of arcs on a circle. A graph G = (V,E) is called a circular‐arc overlap graph for S if (i) there is a one‐to‐one correspondence between V and S and (ii) two vertices in V are adjacent if and only if the corresponding arcs in S intersect but neither one of them contains the other. In this article, we present two polynomial time algorithms on circular‐arc overlap graphs. Given a circular‐arc overlap graph in the form of a family of n arcs, the first algorithm obtains a maximum independent set in O ( n 2 ) time and the second one finds a maximum clique in O ( n 5 ) time.