Path hitting in acyclic graphs
DOI10.1007/s00453-007-9087-5zbMath1176.68244OpenAlexW2056155690MaRDI QIDQ1018049
Publication date: 13 May 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9087-5
linear programmingapproximation algorithmsedge coverprimal-dualedge dominating settree augmentationtree multicut
Programming involving graphs or networks (90C35) Linear programming (90C05) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Partial multicuts in trees
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- On the hardness of approximating Multicut and Sparsest-Cut
- Reductions to 1–matching polyhedra
- A threshold of ln n for approximating set cover
- On the power of unique 2-prover 1-round games
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for Several Graph Augmentation Problems
- A 1-matching blossom-type algorithm for edge covering problems
- Approximation Algorithms for Graph Augmentation
- A General Approximation Technique for Constrained Forest Problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
This page was built for publication: Path hitting in acyclic graphs
