Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
From MaRDI portal
Publication:1935804
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
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
