The problem of finding a maximum weighted stable set in a claw-free graph is a fundamental generalization of the matching problem. It has been therefore investigated by several researchers, and its theory has been developing for more than 40 years. The last 10 years have been particularly productive, mainly due to new approaches that exploit results from structural graph theory. The purpose of this chapter is to help the interested researchers to navigate through the various results in this field and in particular to shed light on the latest achievements and the current open questions.
Stable Sets in Claw- Free Graphs: A Journey Through Algorithms and Polytopes
Ventura P
2011
Abstract
The problem of finding a maximum weighted stable set in a claw-free graph is a fundamental generalization of the matching problem. It has been therefore investigated by several researchers, and its theory has been developing for more than 40 years. The last 10 years have been particularly productive, mainly due to new approaches that exploit results from structural graph theory. The purpose of this chapter is to help the interested researchers to navigate through the various results in this field and in particular to shed light on the latest achievements and the current open questions.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
