A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs

DOI10.1007/11682462_46zbMath1145.05322OpenAlexW1549137733MaRDI QIDQ3525784

Martin Fuerer

Publication date: 18 September 2008

Published in: LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11682462_46

zbMATH Keywords

NP-hardmaximum independent setsparse graphexponential time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

A refined algorithm for maximum independent set in degree-4 graphs ⋮ An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Fast algorithms for max independent set ⋮ Exact algorithms for maximum independent set ⋮ Solving NP-Complete Problems with Quantum Search ⋮ Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3