Geodesic
New Algorithms for Mixed Dominating Set
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open questions. In particular, we settle the problem's complexity parameterized by treewidth and pathwidth by giving an algorithm running in time $O^*(5^{tw})$ (improving the current best $O^*(6^{tw})$), as well as a lower bound showing that our algorithm cannot be improved under the Strong Exponential Time Hypothesis (SETH), even if parameterized by pathwidth (improving a lower bound of $O^*((2 - \varepsilon)^{pw})$). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve both the best known FPT algorithm for this problem, from $O^*(4.172^k)$ to $O^*(3.510^k)$, and the best known exponential-time exact algorithm, from $O^*(2^n)$ and exponential space, to $O^*(1.912^n)$ and polynomial space.
DOI : 10.46298/dmtcs.6824
Classification : 05C69, 05C85 
@article{DMTCS_2021_23_1_a8,
     author = {Dublois, Louis and Lampis, Michael and Paschos, Vangelis Th.},
     title = {New {Algorithms} for {Mixed} {Dominating} {Set}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2021-2022},
     doi = {10.46298/dmtcs.6824},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6824/}
}
TY  - JOUR
AU  - Dublois, Louis
AU  - Lampis, Michael
AU  - Paschos, Vangelis Th.
TI  - New Algorithms for Mixed Dominating Set
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6824/
DO  - 10.46298/dmtcs.6824
LA  - en
ID  - DMTCS_2021_23_1_a8
ER  - 
%0 Journal Article
%A Dublois, Louis
%A Lampis, Michael
%A Paschos, Vangelis Th.
%T New Algorithms for Mixed Dominating Set
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6824/
%R 10.46298/dmtcs.6824
%G en
%F DMTCS_2021_23_1_a8
Dublois, Louis; Lampis, Michael; Paschos, Vangelis Th. New Algorithms for Mixed Dominating Set. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 1. doi : 10.46298/dmtcs.6824. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6824/

Cité par Sources :