Two fixed-parameter algorithms for vertex covering by paths on trees

DOI10.1016/J.IPL.2007.10.007MaRDI QIDQ963337zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Rolf Niedermeier, Johannes Uhlmann

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.10.007

zbMATH Keywords

exact algorithmsgraph algorithmsfixed-parameter tractabilitycombinatorial problemsvertex covering,covering trees by pathsweighted hitting set

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the minimum vertex k-path cover of trees
• The approximability of partial vertex covers in trees
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• On approximability of connected path vertex cover
• On covering vertices of a graph by trees
• Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
• Vertex cover and edge-vertex domination in trees
• Vertex covering with capacitated trees
• On the parameterized complexity of spanning trees with small vertex covers
• Covering a tree with rooted subtrees -- parameterized and approximation algorithms

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A general method to speed up fixed-parameter-tractable algorithms
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Augmentation Problems
• Fixed-parameter tractability and data reduction for multicut in trees
• Kernelization and Complexity Results for Connectivity Augmentation Problems
• Vertex covering by paths on trees with its applications in machine translation

Cited in

(6)

• Exact algorithms and applications for tree-like Weighted Set Cover
• Vertex covering by paths on trees with its applications in machine translation
• Algorithms and Data Structures
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
• Treewidth and pathwidth parameterized by the vertex cover number

This page was built for publication: Two fixed-parameter algorithms for vertex covering by paths on trees

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