On the parameterized complexity of spanning trees with small vertex covers

DOI10.1007/978-3-030-39219-2_34MaRDI QIDQ779245zbMATH OpenOpenAlexFDO

Authors Chamanvir Kaur, Neeldhara Misra

Publication date 21 July 2020

Full work available at URL https://doi.org/10.1007/978-3-030-39219-2_34

zbMATH Keywords

spanning treestreewidthvertex cover

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized complexity of the spanning tree congestion problem
• Algorithms and Data Structures
• On the vertex cover \(P_3\) problem parameterized by treewidth

Cited in

(5)

• Algorithms and Data Structures
• An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth
• Two fixed-parameter algorithms for vertex covering by paths on trees
• Grundy distinguishes treewidth from pathwidth
• Grundy Distinguishes Treewidth from Pathwidth

This page was built for publication: On the parameterized complexity of spanning trees with small vertex covers

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