A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs

DOI10.1007/978-3-540-68891-4_6zbMath1143.05333OpenAlexW2113511711MaRDI QIDQ3503841

Gianpaolo Oriolo, Ugo Pietropaoli, Gautier Stauffer

Publication date: 10 June 2008

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2108/38718

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Structure of squares and efficient domination in graph classes ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants) ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\) ⋮ Unnamed Item ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ 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 ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ On the Stable Set Polytope of Claw-Free Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• 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
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Compositions for perfect graphs
• TWO THEOREMS IN GRAPH THEORY
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs