A win-win algorithm for the (k+1)-LST/k-pathwidth problem

DOI10.33048/DAIO.2021.28.710zbMATH Open1496.05027OpenAlexW4205762140MaRDI QIDQ5100142FDOQ5100142

Authors: Artëm Gennadievich Klyuchikov, Mikhail Vyalyi 

Publication date: 29 August 2022

Published in: Diskretnyi analiz i issledovanie operatsii (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/da1288

Recommendations

• scientific article; zbMATH DE number 4173000
• scientific article; zbMATH DE number 176762
• The \(k\)-leaf spanning tree problem admits a klam value of 39
• An improved algorithm for finding tree decompositions of small width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

zbMATH Keywords

spanning treeFPTpath decomposition\(k\)-LST problemwin-win algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38)

Cites Work

• Quickly excluding a forest
• NP-completeness and degree restricted spanning trees
• Graph Minors I: A Short Proof of the Path-width Theorem

This page was built for publication: A win-win algorithm for the \((k+1)\)-LST/\(k\)-pathwidth problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5100142)