Partial multicuts in trees
From MaRDI portal
Publication:861281
DOI10.1016/j.tcs.2006.09.018zbMath1140.90046OpenAlexW2138694041MaRDI QIDQ861281
Publication date: 9 January 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.09.018
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (11)
Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ An approximation algorithm for \(P\)-prize-collecting set cover problem ⋮ A unified approach to approximating partial covering problems ⋮ An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ The checkpoint problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Path hitting in acyclic graphs ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ On the parameterized complexity of separating certain sources from the target
Cites Work
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Strongly polynomial-time approximation for a class of bicriteria problems.
- On the hardness of approximating Multicut and Sparsest-Cut
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- A threshold of ln n for approximating set cover
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A new greedy approach for facility location problems
- On the power of unique 2-prover 1-round games
- Approximating the k-multicut problem
- Combinatorial Optimization with Rational Objective Functions
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- The Complexity of Multiterminal Cuts
- Approximation algorithms for partial covering problems
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- A Unified Approach to Approximating Partial Covering Problems
- Algorithms - ESA 2003
This page was built for publication: Partial multicuts in trees
