Approximation algorithms for \(k\)-hurdle problems

DOI10.1007/s00453-010-9408-yzbMath1213.68436MaRDI 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 algorithm; randomized rounding; multicut; multiway cut

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

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