A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)

DOI10.1007/978-3-642-11440-3_26zbMATH Open1274.68678OpenAlexW1526809436MaRDI QIDQ3404455FDOQ3404455

Authors: Mingyu Xiao 

Publication date: 9 February 2010

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11440-3_26

Recommendations

• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)
• Exact Algorithms for Maximum Independent Set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Cited In (18)

• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)
• Parameterized edge dominating set in cubic graphs (extended abstract)
• Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
• Maximum independent sets in graphs of low degree
• A refined algorithm for maximum independent set in degree-4 graphs
• New parameterized algorithms for the edge dominating set problem
• An exact algorithm for maximum independent set in degree-5 graphs
• On the Independence Number of Graphs with Maximum Degree 3
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• On the maximum independent set problem in graphs of bounded maximum degree
• Faster graph coloring in polynomial space
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Exact algorithms for maximum independent set
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Parameterized edge dominating set in graphs with degree bounded by 3

This page was built for publication: A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)

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