Solving the weighted stable set problem in claw-free graphs via decomposition
From MaRDI portal
Publication:5501925
Recommendations
- scientific article; zbMATH DE number 6783420
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-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
Cites work
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A Local Strengthening of Reed's \omega, \Delta, \chi Conjecture for Quasi-line Graphs
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- A reduction 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
- A strengthening of Ben Rebea's lemma
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Claw-free graphs. IV: Decomposition theorem
- Claw-free graphs. V. Global structure
- Claw-free graphs. VII. Quasi-line graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Finding a smallest odd hole in a claw-free graph using global structure
- Finding and counting small induced subgraphs efficiently
- scientific article; zbMATH DE number 432790 (Why is no real title available?)
- scientific article; zbMATH DE number 1263275 (Why is no real title available?)
- Maximum matching and a polyhedron with 0,1-vertices
- Minimum weighted clique cover on strip-composed perfect graphs
- Network flows. Theory, algorithms, and applications.
- On claw-free asteroidal triple-free graphs
- On linear and circular structure of (claw, net)-free graphs
- On maximal independent sets of vertices in claw-free graphs
- On the recognition of fuzzy circular interval graphs
- The stable set polytope of quasi-line graphs
- The structure of claw-free graphs
Cited in
(33)- Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
- Equimatchable claw-free graphs
- Reconfiguration in bounded bandwidth and tree-depth
- Colouring squares of claw-free graphs
- 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\)
- Separation routine and extended formulations for the stable set problem in claw-free graphs
- Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
- Disconnected cuts in claw-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
- Polynomial size IP formulations of knapsack may require exponentially large coefficients
- On the facets of stable set polytopes of circular interval graphs
- Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
- 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
- scientific article; zbMATH DE number 1187143 (Why is no real title available?)
- Colouring squares of claw-free graphs
- Counting weighted independent sets beyond the permanent
- Disconnected cuts in claw-free graphs
- Complexity and polynomially solvable special cases of QUBO
- scientific article; zbMATH DE number 6783420 (Why is no real title available?)
- Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs
- Combining decomposition approaches for the maximum weight stable set problem
- Minimum weighted clique cover on claw‐free perfect graphs
- Linear‐time algorithms for eliminating claws in graphs
- A polytime preprocess algorithm for the maximum independent set problem
- Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
- Counting kernels in directed graphs with arbitrary orientations
- Getting linear time in graphs of bounded neighborhood diversity
- The total matching polytope of complete bipartite graphs
This page was built for publication: Solving the weighted stable set problem in claw-free graphs via decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501925)
