Wyszukiwarka
Abstrakt
In this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding a minimum secondary dominating set in trees is presented.
Cytowania
-
2
CrossRef
-
0
Web of Science
-
2
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 74 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00453-023-01192-2
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
ALGORITHMICA
ISSN: 0178-4617 - Język:
- angielski
- Rok wydania:
- 2023
- Opis bibliograficzny:
- Raczek J.: Complexity Issues on of Secondary Domination Number// ALGORITHMICA -, (2023),
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s00453-023-01192-2
- Źródła finansowania:
-
- Publikacja bezkosztowa
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 75 razy
Publikacje, które mogą cię zainteresować
On the connected and weakly convex domination numbers
- M. Lemańska,
- M. Dettlaff,
- D. Osula
- + 1 autorów
2020
Collaborative Exploration of Trees by Energy-Constrained Mobile Robots
- S. Das,
- D. Dereniowski,
- C. Karousatou
2018