|
A win-win algorithm for the $(k+1)$-LST/$k$-pathwidth problem
A. G. Klyuchikova, M. N. Vyalyiabc a Moscow Institute of Physics and Technology, 9 Institutskii Lane, 141701 Dolgoprudnyi, Russia
b Federal Research Center “Computer Science and Control” RAS 44 Bld. 2 Vavilov Street, 119333 Moscow, Russia
c HSE University, 11 Pokrovskii Boulevard, 109028 Moscow, Russia
Abstract:
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, FPT.
Received: 12.04.2021 Revised: 02.08.2021 Accepted: 03.08.2021
Citation:
A. G. Klyuchikov, M. N. Vyalyi, “A win-win algorithm for the $(k+1)$-LST/$k$-pathwidth problem”, Diskretn. Anal. Issled. Oper., 28:4 (2021), 117–124
Linking options:
https://www.mathnet.ru/eng/da1288 https://www.mathnet.ru/eng/da/v28/i4/p117
|
Statistics & downloads: |
Abstract page: | 154 | Full-text PDF : | 50 | References: | 15 | First page: | 3 |
|