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 30 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
- Bibliografia: test
-
więcej (3) mniej
- Haynes T. W., Hedetniemi S. T., Slater P. J.: Fundamentals of domination in graphs. New York, Basel, Hong Kong, Marcel Dekker Inc. 1998. otwiera się w nowej karcie
- Ross K. A., Wright C. R. B.: Matematyka dyskretna. Warszawa, Wydawnictwo Naukowe PWN 1996.
- Handbook of Discrete and Combinatorial Mathematics. Editor-in-Chief: Rosen K. H., London, Washington, D.C. CRC Press Boca Raton 2000. otwiera się w nowej karcie
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 110 razy