An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)

DOI10.1016/j.disopt.2016.01.002zbMath1387.05256arXiv1501.05851OpenAlexW2297117380WikidataQ125579034 ScholiaQ125579034MaRDI QIDQ1751148

Paolo Nobili, Antonio Sassano

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

matchingstable setclaw-free graphsnet-free graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal greedy heuristic to color interval graphs
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• On linear and circular structure of (claw, net)-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
• Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

This page was built for publication: An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)