An output sensitive algorithm for computing a maximum independent set of a circle graph

DOI10.1016/j.ipl.2010.05.016zbMath1234.68483OpenAlexW2124809079WikidataQ56503311 ScholiaQ56503311MaRDI QIDQ765500

David Gregg, Nicholas Nash

Publication date: 19 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10344/2228

zbMATH Keywords

design of algorithmsgraph algorithmsmaximum independent setmaximum stable setcircle graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ Models and Algorithms for Genome Rearrangement with Positional Constraints ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ Computing maximum independent set on outerstring graphs and their relatives

Cites Work

• New clique and independent set algorithms for circle graphs
• Erratum to: New clique and independent set algorithms for circle graphs
• The complexity of domination problems in circle graphs
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Efficiently implementing maximum independent set algorithms on circle graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: An output sensitive algorithm for computing a maximum independent set of a circle graph