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

DOI10.1016/J.IPL.2010.05.016MaRDI QIDQ765500zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cites work

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

Cited in

(9)

• Computing maximum independent set on outerstring graphs and their relatives
• 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

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)