Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs

DOI10.1016/J.TCS.2012.09.022MaRDI QIDQ1935804zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

exact algorithmindependent setmeasure and conquer

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

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)