An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph | Zendy

Sumio Masuda | Zendy; Kazuo Nakajima | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph

Author(s) -

Sumio Masuda,

Kazuo Nakajima

Publication year - 1988

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0217003

Subject(s) - combinatorics , mathematics , arc (geometry) , graph , independent set , algorithm , set (abstract data type) , feedback arc set , discrete mathematics , line graph , computer science , voltage graph , geometry , programming language

A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only $O(n \cdot \log n)$ time and $O(n)$ space. Furthermore, if the endpoints of the arcs are already sorted, it runs in $O(n)$ time. This algorithm is time- and space-optimal to within a constant factor.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research