A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
DOI10.1007/11682462_46zbMATH Open1145.05322OpenAlexW1549137733MaRDI QIDQ3525784FDOQ3525784
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
Recommendations
- A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
- Algorithms for maximum independent sets
- An O(20.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
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)
Cited In (22)
- A faster algorithm for maximum independent set on interval filament graphs
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- An optimal maximal independent set algorithm for bounded-independence graphs
- 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)
