Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
DOI10.1016/J.TCS.2012.09.022zbMATH Open1259.68263DBLPjournals/tcs/XiaoN13OpenAlexW2159308691WikidataQ56335615 ScholiaQ56335615MaRDI QIDQ1935804FDOQ1935804
Authors: Mingyu Xiao, Hiroshi Nagamochi 
Publication date: 19 February 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.09.022
Recommendations
- 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)\)
- Further Improvement on Maximum Independent Set in Degree-4 Graphs
- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
- Exact algorithms for maximum independent set
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (18)
- Above guarantee parameterization for vertex cover on graphs with maximum degree 4
- 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
- Exponential upper bounds for the runtime of randomized search heuristics
- Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
- Advice complexity of adaptive priority algorithms
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- An exact algorithm for maximum independent set in degree-5 graphs
- A refined exact algorithm for edge dominating set
- On the power of simple reductions for the maximum independent set problem
- Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
- Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
- Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
- Exact algorithms for maximum independent set
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
This page was built for publication: Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1935804)
