Geodesic
Parameterized Complexity of Geodetic Set
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 401-419.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A vertex set $S$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two vertices in $S$. Given a graph $G$ and $k \in \mathbb{N}$, the NP-hard ${\rm G{\small EODETIC}~S{ \small ET}}$ problem asks whether there is a geodetic set of size at most $k$. Complementing various works on ${\rm G{\small EODETIC}~S{ \small ET}}$ restricted to special graph classes, we initiate a parameterized complexity study of ${\rm G{\small EODETIC}~S{ \small ET}}$ and show, on the one side, that ${\rm G{\small EODETIC}~S{ \small ET}}$ is $W[1]$-hard when parameterized by feedback vertex number, path-width, and solution size, combined. On the other side, we develop fixed-parameter algorithms with respect to the feedback edge number, the tree-depth, and the modular-width of the input graph. 
@article{JGAA_2022_26_4_a0,
     author = {Leon Kellerhals and Tomohiro Koana},
     title = {Parameterized {Complexity} of {Geodetic} {Set}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {401--419},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2022},
     doi = {10.7155/jgaa.00601},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00601/}
}
TY  - JOUR
AU  - Leon Kellerhals
AU  - Tomohiro Koana
TI  - Parameterized Complexity of Geodetic Set
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 401
EP  - 419
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00601/
DO  - 10.7155/jgaa.00601
LA  - en
ID  - JGAA_2022_26_4_a0
ER  - 
%0 Journal Article
%A Leon Kellerhals
%A Tomohiro Koana
%T Parameterized Complexity of Geodetic Set
%J Journal of Graph Algorithms and Applications
%D 2022
%P 401-419
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00601/
%R 10.7155/jgaa.00601
%G en
%F JGAA_2022_26_4_a0
Leon Kellerhals; Tomohiro Koana. Parameterized Complexity of Geodetic Set. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 401-419. doi : 10.7155/jgaa.00601. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00601/

Cité par Sources :