Efficiently implementing maximum independent set algorithms on circle graphs

DOI10.1145/1412228.1455265MaRDI QIDQ5406178zbMATH OpenOpenAlexFDO

Authors Nicholas Nash, Sylvain Lelait, David Gregg

Publication date 1 April 2014

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1412228.1455265

zbMATH Keywords

circle graphmaximum independent setmaximum stable set

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• New clique and independent set algorithms for circle graphs
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
• An output sensitive algorithm for computing a maximum independent set of a circle graph
• Algorithms and Computation
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph

Cited in

(5)

• New clique and independent set algorithms for circle graphs
• Counting hexagonal patches and independent sets in circle graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• An output sensitive algorithm for computing a maximum independent set of a circle graph

This page was built for publication: Efficiently implementing maximum independent set algorithms on circle graphs

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