Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
From MaRDI portal
Publication:5501925
DOI10.1145/2629600zbMath1321.05260OpenAlexW2029471776WikidataQ56335607 ScholiaQ56335607MaRDI QIDQ5501925
Yuri Faenza, Gianpaolo Oriolo, Gautier Stauffer
Publication date: 14 August 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2629600
Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\) ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ Equimatchable 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 ⋮ Disconnected cuts in claw-free graphs ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Minimum weighted clique cover on claw‐free perfect graphs ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Colouring squares of claw-free 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 ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Unnamed Item ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ Colouring Squares of Claw-free Graphs ⋮ An \(\mathcal{O} (n^2 \log{n})\) 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\) ⋮ 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 ⋮ Extended formulations from communication protocols in output-efficient time ⋮ Counting Weighted Independent Sets beyond the Permanent
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- On the recognition of fuzzy circular interval graphs
- Claw-free graphs. IV: Decomposition theorem
- The stable set polytope of quasi-line graphs
- Claw-free graphs. V. Global structure
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- A strengthening of Ben Rebea's lemma
- On linear and circular structure of (claw, net)-free graphs
- On claw-free asteroidal triple-free graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Claw-free graphs. VII. Quasi-line graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Finding a smallest odd hole in a claw-free graph using global structure
- A reduction algorithm for the weighted stable set problem in claw-free graphs
- Domination When the Stars Are Out
- Asymptotics of the chromatic number for quasi-line graphs
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs
- A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs
- Maximum matching and a polyhedron with 0,1-vertices
