License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.37
URN: urn:nbn:de:0030-drops-133812
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13381/
Bousquet, Nicolas ;
Joffard, Alice ;
Ouvrard, Paul
Linear Transformations Between Dominating Sets in the TAR-Model
Abstract
Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = ⟨ D₀ = D_s, D₁ …, D_? = D_t ⟩ of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k.
We first improve a result of Haas and Seyffarth [R. Haas and K. Seyffarth, 2017], by showing that if k = Γ(G)+α(G)-1 (where Γ(G) is the maximum size of a minimal dominating set and α(G) the maximum size of an independent set), then there exists a linear TAR reconfiguration sequence between any pair of dominating sets.
We then improve these results on several graph classes by showing that the same holds for K_?-minor free graph as long as k ≥ Γ(G)+O(? √(log ?)) and for planar graphs whenever k ≥ Γ(G)+3. Finally, we show that if k = Γ(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.
BibTeX - Entry
@InProceedings{bousquet_et_al:LIPIcs:2020:13381,
author = {Nicolas Bousquet and Alice Joffard and Paul Ouvrard},
title = {{Linear Transformations Between Dominating Sets in the TAR-Model}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {37:1--37:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-173-3},
ISSN = {1868-8969},
year = {2020},
volume = {181},
editor = {Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13381},
URN = {urn:nbn:de:0030-drops-133812},
doi = {10.4230/LIPIcs.ISAAC.2020.37},
annote = {Keywords: reconfiguration, dominating sets, addition removal, connectivity, diameter, minor, treewidth}
}
|
Keywords: |
|
reconfiguration, dominating sets, addition removal, connectivity, diameter, minor, treewidth |
|
Collection: |
|
31st International Symposium on Algorithms and Computation (ISAAC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
