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

DOI10.1016/j.ipl.2007.10.007zbMath1185.05115OpenAlexW2136446235MaRDI QIDQ963337

Jiong Guo, Johannes Uhlmann, Rolf Niedermeier

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

combinatorial problemsgraph algorithmsfixed-parameter tractabilityexact algorithmsvertex covering,covering trees by pathsweighted hitting set

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Vertex covering by paths on trees with its applications in machine translation
• A general method to speed up fixed-parameter-tractable algorithms
• Fixed-parameter tractability and data reduction for multicut in trees
• Kernelization and Complexity Results for Connectivity Augmentation Problems
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Augmentation Problems

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