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

DOI10.33048/DAIO.2021.28.710MaRDI QIDQ5100142zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)