Approximation algorithms for \(k\)-hurdle problems

DOI10.1007/s00453-010-9408-yzbMath1213.68436OpenAlexW1979224980MaRDI QIDQ627530

Brian C. Dean, Adam Whitley, Adam Griffis, Ojas Parekh

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9408-y

zbMATH Keywords

approximation algorithmrandomized roundingmulticutmultiway cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A polynomial-time simplex method for the maximum \(k\)-flow problem
• Packing and covering a tree by subtrees
• An improved approximation algorithm of MULTIWAY CUT.
• Deterministic network interdiction
• Optimal 3-terminal cuts and linear programming
• On budget-constrained flow improvement.
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Finding Minimum-Cost Circulations by Successive Approximation
• Approximating the k-multicut problem
• Optimal attack and reinforcement of a network
• Maximizing the minimum source-sink path subject to a budget constraint
• The Complexity of Multiterminal Cuts
• Disjoint (s, t)‐cuts in a network
• Shortest-path network interdiction
• Multiway cuts in node weighted graphs
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• The network inhibition problem
• Algorithm Theory - SWAT 2004
• Approximation and Online Algorithms
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem