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

DOI10.1016/j.tcs.2012.09.022zbMath1259.68263OpenAlexW2159308691WikidataQ56335615 ScholiaQ56335615MaRDI QIDQ1935804

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

independent setexact algorithmmeasure 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)

Related Items (16)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Finding near-optimal independent sets at scale ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ 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 ⋮ Advice complexity of adaptive priority algorithms ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ 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 ⋮ A refined exact algorithm for edge dominating set ⋮ Exact algorithms for maximum independent set ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4 ⋮ 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