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 30 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
- Bibliography: test
-
show (3) hide
- Haynes T. W., Hedetniemi S. T., Slater P. J.: Fundamentals of domination in graphs. New York, Basel, Hong Kong, Marcel Dekker Inc. 1998. open in new tab
- 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. open in new tab
- Verified by:
- Gdańsk University of Technology
seen 110 times