Geodesic
A win-win algorithm for~the~$(k+1)$-LST/$k$-pathwidth~problem
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 4, pp. 117-124

Voir la notice de l'article provenant de la source Math-Net.Ru

We describe a win-win algorithm that produces in polynomial of size of a graph $G$ and given parameter $k$ time either a spanning tree with al least $k+1$ leaves or a path decomposition with width at most $k$. This algorithm is optimal due to the path decomposition theorem [1]. Bibliogr. 5.
Keywords: path decomposition, spanning tree, $k$-LST problem, win-win algorithm
Mots-clés : FPT. 
@article{DA_2021_28_4_a4,
     author = {A. G. Klyuchikov and M. N. Vyalyi},
     title = {A win-win algorithm for~the~$(k+1)${-LST/}$k$-pathwidth~problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {117--124},
     publisher = {mathdoc},
     volume = {28},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_4_a4/}
}
TY  - JOUR
AU  - A. G. Klyuchikov
AU  - M. N. Vyalyi
TI  - A win-win algorithm for~the~$(k+1)$-LST/$k$-pathwidth~problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 117
EP  - 124
VL  - 28
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_4_a4/
LA  - ru
ID  - DA_2021_28_4_a4
ER  - 
%0 Journal Article
%A A. G. Klyuchikov
%A M. N. Vyalyi
%T A win-win algorithm for~the~$(k+1)$-LST/$k$-pathwidth~problem
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 117-124
%V 28
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_4_a4/
%G ru
%F DA_2021_28_4_a4
A. G. Klyuchikov; M. N. Vyalyi. A win-win algorithm for~the~$(k+1)$-LST/$k$-pathwidth~problem. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 4, pp. 117-124. http://geodesic.mathdoc.fr/item/DA_2021_28_4_a4/