Approximation Algorithms for k-Hurdle Problems

DOI10.1007/978-3-540-78773-0_39MaRDI QIDQ5458550zbMATH OpenOpenAlexFDO

Authors Brian C. Dean, Adam Griffis, Adam Whitley

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_39

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for \(k\)-hurdle problems
• scientific article; zbMATH DE number 1775387
• Generalized \(k\)-multiway cut problems
• Improved region-growing and combinatorial algorithms for \(k\)-route cut problems (extended abstract)
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 2050722 (Why is no real title available?)
• scientific article; zbMATH DE number 1487883 (Why is no real title available?)
• A polynomial-time simplex method for the maximum \(k\)-flow problem
• Algorithm Theory - SWAT 2004
• An improved approximation algorithm of MULTIWAY CUT.
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximating the k-multicut problem
• Approximation and Online Algorithms
• Deterministic network interdiction
• Disjoint (s, t)‐cuts in a network
• Finding Minimum-Cost Circulations by Successive Approximation
• Maximizing the minimum source-sink path subject to a budget constraint
• Multiway cuts in node weighted graphs
• On budget-constrained flow improvement.
• Optimal 3-terminal cuts and linear programming
• Optimal attack and reinforcement of a network
• Packing and covering a tree by subtrees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Shortest-path network interdiction
• The Complexity of Multiterminal Cuts
• The network inhibition problem

Cited in

(3)

• Improved region-growing and combinatorial algorithms for \(k\)-route cut problems (extended abstract)
• Approximation algorithms for \(k\)-hurdle problems
• The checkpoint problem

This page was built for publication: Approximation Algorithms for k-Hurdle Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458550)