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

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

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

(20)

• A refined algorithm for maximum independent set in degree-4 graphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• Exact algorithms for maximum independent set
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• Exponential upper bounds for the runtime of randomized search heuristics
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• On the power of simple reductions for the maximum independent set problem
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)
• A refined exact algorithm for edge dominating set
• Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Advice complexity of adaptive priority algorithms
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• A faster algorithm for vertex cover parameterized by solution size
• PACE solver description: reductions and heuristic search for the dominating set problem and the hitting set problem
• An exact algorithm for maximum independent set in degree-5 graphs
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover

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)