Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
From MaRDI portal
Publication:4877516
DOI10.1137/S0097539793243016zbMath0844.68061OpenAlexW2044343300WikidataQ56030329 ScholiaQ56030329MaRDI QIDQ4877516
Vijay V. Vazirani, Naveen Garg, Mihalis Yannakakis
Publication date: 13 May 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793243016
Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)
Related Items (77)
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ On the (near) optimality of extended formulations for multi-way cut in social networks ⋮ Approximating the maximum agreement forest on \(k\) trees ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Fast First-Order Algorithms for Packing–Covering Semidefinite Programs ⋮ Approximation algorithms for requirement cut on graphs ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ The maximum integer multiterminal flow problem in directed graphs ⋮ EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS ⋮ Partial multicuts in trees ⋮ Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Clique Cover and Graph Separation ⋮ Metric decompositions of path-separable graphs ⋮ The multi-multiway cut problem ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Vertex downgrading to minimize connectivity ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ Unnamed Item ⋮ Approximation and hardness results for label cut and related problems ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ A unified approach to approximating partial covering problems ⋮ Multicut Is FPT ⋮ Unnamed Item ⋮ Models and methods for solving the problem of network vulnerability ⋮ Restricted vertex multicut on permutation graphs ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ Finding the closest ultrametric ⋮ Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Multi-Budgeted Directed Cuts ⋮ On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ The Complexity and Approximability of Minimum Contamination Problems ⋮ Approximating Requirement Cut via a Configuration LP ⋮ Disjoint paths in sparse graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Min sum clustering with penalties ⋮ The multi-terminal maximum-flow network-interdiction problem ⋮ The checkpoint problem ⋮ Unnamed Item ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Correlation clustering in general weighted graphs ⋮ Constant ratio fixed-parameter approximation of the edge multicut problem ⋮ Approximation algorithms for the Bipartite Multicut problem ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Approximation Algorithms for k-Hurdle Problems ⋮ Robust Critical Node Selection by Benders Decomposition ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Path hitting in acyclic graphs ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Approximation algorithms for min-sum \(p\)-clustering ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ An improved approximation algorithm of MULTIWAY CUT. ⋮ Multicuts and integral multiflows in rings ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ Multi-budgeted directed cuts ⋮ Clustering with qualitative information ⋮ Approximating a generalization of MAX 2SAT and MIN 2SAT ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ Logical analysis of data with decomposable structures. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs ⋮ A greedy algorithm for multicut and integral multiflow in rooted trees ⋮ On local search for the generalized graph coloring problem
This page was built for publication: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
