NP-completeness of convex and weakly convex domiating set decision problems.

Joanna Raczek

NP-completeness of convex and weakly convex domiating set decision problems.

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.

Author (1)

Joanna Raczek dr inż.

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