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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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)

• Grundy Distinguishes Treewidth from Pathwidth
• Grundy distinguishes treewidth from pathwidth
• 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

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)