Polynomial time algorithms on circular‐arc overlap graphs | Zendy

Kashiwabara Toshinobu | Zendy; Masuda Sumio | Zendy; Nakajima Kazuo | Zendy; Fujisawa Toshio | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research