An O(m n) algorithm for the weighted stable set problem in claw-free graphs with (G) 3

DOI10.1007/S10107-016-1080-9MaRDI QIDQ2364488zbMATH OpenOpenAlexFDO

Authors Paolo Nobili, Antonio Sassano

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

zbMATH Keywords

algorithmsclaw-free graphsstable set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Abstract: In this paper we show how to solve the emph{Maximum Weight Stable Set Problem} in a claw-free graph $G(V,E)$ with $alpha(G)le3$ in time $calO(|E|log|V|)$. More precisely, in time $calO(|E|)$ we check whether $alpha(G)le3$ or produce a stable set with cardinality at least $4$; moreover, if $alpha(G)le3$ we produce in time $calO(|E|log|V|)$ a maximum stable set of $G$. This improves the bound of $calO(|E||V|)$ due to Faenza et al.

Recommendations

• scientific article; zbMATH DE number 6783420
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• A reduction 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\)
• Solving the weighted stable set problem in claw-free graphs via decomposition

Cites work

• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• Finding and counting small induced subgraphs efficiently
• Solving the weighted stable set problem in claw-free graphs via decomposition
• The structure of claw-free graphs
• TWO THEOREMS IN GRAPH THEORY

Cited in

(17)

• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Maximum weight independent set for 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\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• New results on independent sets in extensions of \(2K_2\)-free graphs
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• A reduction algorithm for the weighted stable set problem in claw-free graphs
• The stable set problem and the thinness of a graph
• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• A sufficient condition to extend polynomial results for the maximum independent set problem
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• scientific article; zbMATH DE number 3893237 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• Solving the weighted stable set problem in claw-free graphs via decomposition
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs

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\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364488)