Two fixed-parameter algorithms for vertex covering by paths on trees
DOI10.1016/J.IPL.2007.10.007zbMATH Open1185.05115OpenAlexW2136446235MaRDI QIDQ963337FDOQ963337
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
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
exact algorithmsgraph algorithmsfixed-parameter tractabilitycombinatorial problemsvertex covering,covering trees by pathsweighted hitting set
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)
Cites Work
- Title not available (Why is that?)
- Fixed-parameter tractability and data reduction for multicut in trees
- Augmentation Problems
- 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
- Vertex covering by paths on trees with its applications in machine translation
- Kernelization and Complexity Results for Connectivity Augmentation Problems
Cited In (6)
- Algorithms and Data Structures
- Vertex covering by paths on trees with its applications in machine translation
- 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
- Exact algorithms and applications for tree-like Weighted Set Cover
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)
