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

DOI10.1016/J.TCS.2015.06.030MaRDI QIDQ897955zbMATH OpenOpenAlexFDO

Authors Jie You, Jianxin Wang, Qilong Feng, 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

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

Recommendations

• On star-cover and path-cover of a tree
• Two fixed-parameter algorithms for vertex covering by paths on trees
• Packing and covering a tree by subtrees
• Covering tree with stars
• Parameterized and Exact Computation

Cites work

• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445367 (Why is no real title available?)
• A survey on tree edit distance and related problems
• Algorithms for parameterized maximum agreement forest problem on multiple trees
• Combinatorial and computational aspects of graph packing and graph decomposition
• Covering tree with stars
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Minimum node disjoint path covering for circular-arc graphs
• On the minimum common integer partition problem
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm
• Some MAX SNP-hard results concerning unordered labeled trees
• Vertex cover: Further observations and further improvements

Cited in

(9)

• scientific article; zbMATH DE number 6739965 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• scientific article; zbMATH DE number 1837688 (Why is no real title available?)
• Two fixed-parameter algorithms for vertex covering by paths on trees
• scientific article; zbMATH DE number 1878047 (Why is no real title available?)
• On star-cover and path-cover of a tree
• Fixed-parameter tractability for the tree assembly problem
• Covering tree with stars
• Exact algorithms and applications for tree-like Weighted Set Cover

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

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