Wyszukiwarka
Abstrakt
Liczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.
Cytuj jako
Pełna treść
pobierz publikację
pobrano 53 razy
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Opuscula Mathematica
nr 24,
strony 189 - 196,
ISSN: 1232-9274 - Rok wydania:
- 2004
- Opis bibliograficzny:
- Raczek J.: NP-completeness of convex and weakly convex domiating set decision problems.// Opuscula Mathematica. -Vol. 24., iss. 2 (2004), s.189-196
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 156 razy