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

DOI10.1007/S10107-016-1080-9zbMATH Open1367.05161arXiv1501.05773OpenAlexW2548429154MaRDI QIDQ2364488FDOQ2364488

Authors: Paolo Nobili, Antonio Sassano 

Publication date: 21 July 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1501.05773

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

zbMATH Keywords

algorithmsclaw-free graphsstable set

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• A reduction 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\)
• The stable set problem and the thinness of a graph
• A New Algorithm for the Maximum 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\)
• 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
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time

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)