A reduction algorithm for the weighted stable set problem in claw-free graphs

DOI10.1016/J.DAM.2013.10.015MaRDI QIDQ2448908zbMATH OpenOpenAlexFDO

Authors Paolo Nobili, Antonio Sassano

Publication date 5 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.10.015

zbMATH Keywords

augmenting pathclaw-free graphsclique reductionmatchingstable set

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• 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
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs
• scientific article; zbMATH DE number 6783420
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• Separation routine and extended formulations for the stable set problem in claw-free graphs
• A combinatorial algorithm for weighted stable sets in bipartite graphs

Cites work

• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A strengthening of Ben Rebea's lemma
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 1263275 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• scientific article; zbMATH DE number 3102314 (Why is no real title available?)
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• Paths, Trees, and Flowers
• The structure of claw-free graphs
• TWO THEOREMS IN GRAPH THEORY

Cited in

(12)

• Maximum weight independent set for claw-free graphs in polynomial time
• An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
• An augmentation algorithm for the maximum weighted stable set problem
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Reductions for the stable set problem
• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• 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 6783420 (Why is no real title available?)
• Solving the weighted stable set problem in claw-free graphs via decomposition
• A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)

This page was built for publication: A reduction algorithm for the weighted stable set problem in claw-free graphs

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