G-2002-42
Finding Augmenting Chains in Extensions of Claw-Free Graphs
, et référence BibTeX
Finding augmenting chains is in the heart of the maximum matching problem, which is equivalent to the maximum stable set problem in the class of line graphs. Due to the celebrated result of Edmonds, augmenting chains can be found in line graphs in polynomial time. Minty and Sbihi generalized this result to claw-free graphs. In this paper we extend it to larger classes. As a particular consequence, a new polynomially solvable case for the maximum stable set problem has been detected.
Paru en août 2002 , 10 pages
Axe de recherche
Publication
jan. 2003
Finding augmenting chains in extensions of claw-free graphs
, et
Information Processing Letters, 86(6), 311–316, 2003
référence BibTeX