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

DOI10.1016/J.IPL.2010.05.016zbMATH Open1234.68483DBLPjournals/ipl/NashG10OpenAlexW2124809079WikidataQ56503311 ScholiaQ56503311MaRDI QIDQ765500FDOQ765500

Authors: Nicholas Nash, David Gregg 

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

Recommendations

• Algorithms and Computation
• New clique and independent set algorithms for circle graphs
• Finding a maximum set of independent chords in a circle
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Efficiently implementing maximum independent set algorithms on circle graphs

zbMATH Keywords

graph algorithmsmaximum independent setdesign of algorithmsmaximum stable setcircle graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Models and algorithms for genome rearrangement with positional constraints
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• A maximum weight clique algorithm for dense circle graphs with many shared endpoints
• Finding a Maximum Clique in a Grounded 1-Bend String Graph
• Algorithms and Computation
• Efficiently implementing maximum independent set algorithms on circle graphs
• A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
• Computing maximum independent set on outerstring graphs and their relatives

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

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