An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
From MaRDI portal
Publication:2364488
DOI10.1007/s10107-016-1080-9zbMath1367.05161arXiv1501.05773OpenAlexW2548429154MaRDI QIDQ2364488
Publication date: 21 July 2017
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1501.05773
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (9)
An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\) ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs ⋮ An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
Cites Work
This page was built for publication: An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
