Efficiently implementing maximum independent set algorithms on circle graphs

DOI10.1145/1412228.1455265zbMath1284.05305OpenAlexW2019602046MaRDI QIDQ5406178

Nicholas Nash, David Gregg, Sylvain Lelait

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

maximum independent setmaximum stable setcircle graph

Mathematics Subject Classification ID

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

Related Items (2)

Counting hexagonal patches and independent sets in 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