Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

DOI10.1002/(SICI)1097-0037(199608)28:1%3C15::AID-NET3%3E3.0.CO;2-GMaRDI QIDQ5689814zbMATH OpenOpenAlexFDO

Authors

Publication date 7 January 1997

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199608)28:1%3C15::aid-net3%3E3.0.co;2-g

zbMATH Keywords

circular-arc graphsmaximum independent sets

Mathematics Subject Classification ID

Communication networks in operations research (90B18)

Recommendations

• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
• Independent Sets in Circular-Arc Graphs

Cited in

(4)

• Finding a maximum set of independent chords in a circle
• Powers of geometric intersection graphs and dispersion algorithms
• An optimal algorithm to find maximum independent set and maximum 2-independent set on cactus graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph

This page was built for publication: Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5689814)