Stable sets for $(P₆,K_{2,3})$-free graphs

Szczegóły
Opis

Tytuł:: Stable sets for $(P₆,K_{2,3})$-free graphs
Autorzy:: Mosca, Raffaele
Powiązania:: https://bibliotekanauki.pl/articles/743743.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph algorithms
stable sets
P₆-free graphs
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 3; 387-401
2083-5892
Język:: angielski
Prawa:: Wszystkie prawa zastrzeżone. Swoboda użytkownika ograniczona do ustawowego zakresu dozwolonego użytku
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.

Informacja

Powiązane pozycje