Reconfiguring Minimum Dominating Sets in Trees - Publikacja - MOST Wiedzy

Wyszukiwarka

Reconfiguring Minimum Dominating Sets in Trees

Abstrakt

We provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining the optimal sequence of “moves” between two minimum dominating sets of a tree.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Cytuj jako

Pełna treść

pobierz publikację
pobrano 13 razy
Wersja publikacji
Accepted albo Published Version
Licencja
Copyright (2020 Journal of Graph Algorithms and Applications)

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuły w czasopismach
Opublikowano w:
Journal of Graph Algorithms and Applications nr 24, strony 47 - 61,
ISSN: 1526-1719
Język:
angielski
Rok wydania:
2020
Opis bibliograficzny:
Lemańska M., Żyliński P.: Reconfiguring Minimum Dominating Sets in Trees// Journal of Graph Algorithms and Applications -Vol. 24,iss. 1 (2020), s.47-61
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.7155/jgaa.00517
Weryfikacja:
Politechnika Gdańska

wyświetlono 11 razy

Publikacje, które mogą cię zainteresować

Meta Tagi