Search
Abstract
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.
Cite as
Full text
download paper
downloaded 53 times
- Publication version
- Accepted or Published Version
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Opuscula Mathematica
no. 24,
pages 189 - 196,
ISSN: 1232-9274 - Publication year:
- 2004
- Bibliographic description:
- Raczek J.: NP-completeness of convex and weakly convex domiating set decision problems.// Opuscula Mathematica. -Vol. 24., iss. 2 (2004), s.189-196
- Verified by:
- Gdańsk University of Technology
seen 156 times