Multiway cuts in directed and node weighted graphs

DOI10.1007/3-540-58201-0_92zbMath1418.68168OpenAlexW1523006294MaRDI QIDQ4632450

Vijay V. Vazirani, Naveen Garg, Mihalis Yannakakis

Publication date: 29 April 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58201-0_92

zbMATH Keywords

polynomial timemulticommodity flowdistance labelcomplementary slackness conditionnode version

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Flows in graphs (05C21)

Related Items

The multi-terminal vertex separator problem: branch-and-cut-and-price, On generalized greedy splitting algorithms for multiway partition problems, Exact and approximation algorithms for sensor placement against DDoS attacks, An extended network interdiction problem for optimal toll control, The maximum integer multiterminal flow problem in directed graphs, Hypergraph Cuts with General Splitting Functions, The complexity of multicut and mixed multicut problems in (di)graphs, The vertex \(k\)-cut problem, FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs, On integer and bilevel formulations for the \(k\)-vertex cut problem, FPT algorithms for path-transversal and cycle-transversal problems, Minimum Violation Vertex Maps and Their Applications to Cut Problems, The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut, A sufficiently fast algorithm for finding close to optimal clique trees, Eisenberg-Gale markets: algorithms and game-theoretic properties, Beating the 2-approximation factor for global bicut, Logical analysis of data with decomposable structures., Unnamed Item, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Maximal Flow Through a Network
• On the multiway cut polyhedron
• The Complexity of Multiterminal Cuts
• Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
• Approximate max-flow min-(multi)cut theorems and their applications