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

DOI10.1016/j.dam.2013.10.015zbMath1288.05284OpenAlexW2082342043MaRDI QIDQ2448908

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

matchingstable setclaw-free graphsaugmenting pathclique reduction

Mathematics Subject Classification ID

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

Related Items (2)

Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Cites Work

• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• A strengthening of Ben Rebea's lemma
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• TWO THEOREMS IN GRAPH THEORY
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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