A reduction algorithm for the weighted stable set problem in claw-free graphs
DOI10.1016/J.DAM.2013.10.015zbMATH Open1288.05284OpenAlexW2082342043MaRDI QIDQ2448908FDOQ2448908
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Matching theory
- Paths, Trees, and Flowers
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The structure of claw-free graphs
- On maximal independent sets of vertices in claw-free graphs
- TWO THEOREMS IN GRAPH THEORY
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- A strengthening of Ben Rebea's lemma
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (12)
- Stable sets in claw-free graphs: a journey through algorithms and polytopes
- An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
- A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
- 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\)
- A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- An augmentation algorithm for the maximum weighted stable set problem
- Reductions for the stable set problem
- Title not available (Why is that?)
- Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
- Solving the weighted stable set problem in claw-free graphs via decomposition
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)
