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

DOI10.1016/J.TCS.2015.06.030zbMATH Open1332.68093OpenAlexW2182492138MaRDI QIDQ897955FDOQ897955

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

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

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)

Cites Work

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

Cited In (7)

• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Title not available (Why is that?)
• Fixed-parameter tractability for the Tree Assembly problem
• Title not available (Why is that?)
• Two fixed-parameter algorithms for vertex covering by paths on trees
• Title not available (Why is that?)
• 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)