Kernelization and parameterized algorithms for covering a tree by a set of stars or paths

DOI10.1016/j.tcs.2015.06.030zbMath1332.68093OpenAlexW2182492138MaRDI QIDQ897955

Qilong Feng, Jianxin Wang, Jie You, Feng Shi

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.030

zbMATH Keywords

graph coveringgraph packingfixed-parameter tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Fixed-parameter tractability for the Tree Assembly problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial and computational aspects of graph packing and graph decomposition
• A survey on tree edit distance and related problems
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Minimum node disjoint path covering for circular-arc graphs
• Some MAX SNP-hard results concerning unordered labeled trees
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• Vertex Cover: Further Observations and Further Improvements
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Covering Tree with Stars
• On the minimum common integer partition problem

This page was built for publication: Kernelization and parameterized algorithms for covering a tree by a set of stars or paths