Efficient algorithms for interval graphs and circular‐arc graphs | Zendy

Gupta U. I. | Zendy; Lee D. T. | Zendy; Leung J. Y.T. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Efficient algorithms for interval graphs and circular‐arc graphs

Author(s) -

Gupta U. I.,

Lee D. T.,

Leung J. Y.T.

Publication year - 1982

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.3230120410

Subject(s) - combinatorics , disjoint sets , mathematics , split graph , interval graph , maximal independent set , interval (graph theory) , cograph , chordal graph , clique , discrete mathematics , independent set , arc (geometry) , indifference graph , clique sum , graph , 1 planar graph , geometry

We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O ( n log n ) time [ O ( n ) time if the endpoints of the intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O ( n 2 ) time, provided again that a corresponding family of arcs is given.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research