Multiway cuts in directed and node weighted graphs

DOI10.1007/3-540-58201-0_92MaRDI QIDQ4632450zbMATH OpenOpenAlexFDO

Authors Naveen Garg, Vijay V. Vazirani, 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

complementary slackness conditiondistance labelmulticommodity flownode versionpolynomial time

Mathematics Subject Classification ID

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

Cites work

• Approximate max-flow min-(multi)cut theorems and their applications
• scientific article; zbMATH DE number 3876616 (Why is no real title available?)
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Maximal Flow Through a Network
• On the multiway cut polyhedron
• Optimization, approximation, and complexity classes
• Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
• The Complexity of Multiterminal Cuts

Cited in

(21)

• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• Logical analysis of data with decomposable structures.
• On generalized greedy splitting algorithms for multiway partition problems
• Exact and approximation algorithms for sensor placement against DDoS attacks
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• Beating the 2-approximation factor for global bicut
• The vertex \(k\)-cut problem
• The maximum integer multiterminal flow problem in directed graphs
• An extended network interdiction problem for optimal toll control
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• The complexity of multicut and mixed multicut problems in (di)graphs
• FPT algorithms for path-transversal and cycle-transversal problems
• Hypergraph Cuts with General Splitting Functions
• Minimum violation vertex maps and their applications to cut problems
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• A sufficiently fast algorithm for finding close to optimal clique trees
• Temporal separators with deadlines
• A mathematical programming approach for recognizing binet matrices
• The multi-terminal vertex separator problem: branch-and-cut-and-price
• Eisenberg-Gale markets: algorithms and game-theoretic properties

This page was built for publication: Multiway cuts in directed and node weighted graphs

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