A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs

DOI10.1007/11682462_46MaRDI QIDQ3525784zbMATH OpenOpenAlexFDO

Authors Martin Fürer

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

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

Recommendations

• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Algorithms for maximum independent sets
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• scientific article; zbMATH DE number 1305487

Cited in

(22)

• A faster algorithm for maximum independent set on interval filament graphs
• An optimal maximal independent set algorithm for bounded-independence graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Extending the MAX algorithm for maximum independent set
• Maximum weight t-sparse set problem on vector-weighted graphs
• Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
• Algorithms for maximum independent sets
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)
• A refined algorithm for maximum independent set in degree-4 graphs
• A linear time algorithm for finding a maximum independent set of a fullerene
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• An optimal algorithm for finding compact sets
• An exact algorithm for maximum independent set in degree-5 graphs
• Solving NP-Complete Problems with Quantum Search
• Fast algorithms for max independent set
• All maximal independent sets and dynamic dominance for sparse graphs
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Exact algorithms for maximum independent set
• Network decomposition and maximum independent set. II: Application research
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Advice complexity of maximum independent set in sparse and bipartite graphs

This page was built for publication: A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs

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