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

DOI10.1137/0217003zbMath0646.68084OpenAlexW2071867466MaRDI QIDQ3790662

Sumio Masuda, Kazuo Nakajima

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1903/4492

zbMATH Keywords

optimal algorithmmaximum independent setcircular-arc graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (25)

A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone ⋮ Optimal separable partitioning in the plane ⋮ Approximating minimum coloring and maximum independent set in dotted interval graphs ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Polygon guarding with orientation ⋮ Maximum weight independent set of circular-arc graph and its application ⋮ Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs ⋮ An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ Linear time algorithms on circular-arc graphs ⋮ Finding an approximate minimum-link visibility path inside a simple polygon ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ A branch and bound algorithm for the maximum clique problem ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Parallel algorithms on circular-arc graphs ⋮ On the complexity of the independent set problem in triangle graphs ⋮ The complexity of dissociation set problems in graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Optimal parallel algorithms on circular-arc graphs ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Efficient reduction for path problems on circular-arc graphs ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The maximum clique problem

This page was built for publication: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph