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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2021},
     volume = {28},
     number = {4},
     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
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
%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/

[1] Bienstock D., Robertson N., Seymour P. D., Thomas R., “Quickly excluding a forest”, J. Comb. Theory, Ser. B, 52 (1991), 274–283 | DOI | Zbl

[2] Douglas R. J., “NP-completeness and degree restricted spanning trees”, Discrete Math., 105:1-3 (1992), 41–47 | DOI | Zbl

[3] Kashiwabara T., Fujisawa T., “NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph”, Proc. Int. Symp. Circuits and Systems (Tokyo, Japan, July 17–19, 1979), IEEE, New York, 1979, 657–660

[4] Bodlaender H. L., Demaine E. D., Fellows M. R. et al., Open problems in parameterized and exact computation — IWPEC 2008, Technical Report UU-CS-2008-017, Utrecht Univ., Utrecht, 2008 (accessed Aug. 3, 2021) http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-017.pdf

[5] Diestel R., “Graph minors I: A short proof of the path-width theorem”, Comb. Prob. Comput., 4:1 (1995), 27–30 | DOI | Zbl