Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

Recommendations

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
Approximate max-integral-flow/min-multicut theorems
Fast approximation algorithms for multicommodity flow problems
Improved bounds on the max-flow min-cut ratio for multicommodity flows

Cited in

(only showing first 100 items - show all)

Path hitting in acyclic graphs
A simple algorithm for multicuts in planar graphs with outer terminals
Multicuts and integral multiflows in rings
Maximum concurrent flows and minimum cuts
Approximation algorithms for min-sum \(p\)-clustering
An improved approximation algorithm of MULTIWAY CUT.
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
Metric decompositions of path-separable graphs
On the Langberg-Médard multiple unicast conjecture
Approximating a generalization of MAX 2SAT and MIN 2SAT
Logical analysis of data with decomposable structures.
A greedy algorithm for multicut and integral multiflow in rooted trees
On local search for the generalized graph coloring problem
An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
Improved bounds on the max-flow min-cut ratio for multicommodity flows
Models and methods for solving the problem of network vulnerability
On complexity, representation and approximation of integral multicommodity flows
Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
Integer plane multiflow maximisation: one-quarter-approximation and gaps
On the (near) optimality of extended formulations for multi-way cut in social networks
The max-flow min-cut property and \(\pm 1\)-resistant sets
Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
Partitioning a graph into small pieces with applications to path transversal
Approximating directed multicuts
Correlation clustering in general weighted graphs
Clustering with qualitative information
Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
The maximum integer multiterminal flow problem in directed graphs
Robust critical node selection by Benders decomposition
Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
Clique Cover and Graph Separation
Parameterized complexity dichotomy for \textsc{Steiner Multicut}
The complexity and approximability of minimum contamination problems
Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Designing FPT algorithms for cut problems using randomized contractions
Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network
Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
Approximate max-integral-flow/min-multicut theorems
Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing
scientific article; zbMATH DE number 45022 (Why is no real title available?)
scientific article; zbMATH DE number 176498 (Why is no real title available?)
Thresholded covering algorithms for robust and max-min optimization
An approximation algorithm for the generalized k-multicut problem
An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Restricted vertex multicut on permutation graphs
Simplex partitioning via exponential clocks and the multiway-cut problem
Approximation and kernelization for chordal vertex deletion
Multicut Is FPT
On the advantage of overlapping clusters for minimizing conductance
Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
Finding the closest ultrametric
An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
Improved approximations for the minimum-cut ratio and the flux
scientific article; zbMATH DE number 867664 (Why is no real title available?)
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
Simplex transformations and the multiway cut problem
Multi-budgeted directed cuts
Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
scientific article; zbMATH DE number 7559431 (Why is no real title available?)
A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
Hallucination helps: energy efficient virtual circuit routing
Streaming Lower Bounds for Approximating MAX-CUT
The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case
A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
Approximation Algorithms for k-Hurdle Problems
Algorithms – ESA 2005
Compression via matroids: a randomized polynomial kernel for odd cycle transversal
Approximation algorithms and hardness of the \(k\)-route cut problem
Approximate duality of multicommodity multiroute flows and cuts: single source case
A measure-theoretical max-flow-min-cut problem
Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
scientific article; zbMATH DE number 7650095 (Why is no real title available?)
A tight bound on approximating arbitrary metrics by tree metrics
Vertex downgrading to minimize connectivity
Approximating Requirement Cut via a Configuration LP
Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
Approximating maximum integral multiflows on bounded genus graphs
Approximation algorithms for \(k\)-hurdle problems
Approximation and hardness results for label cut and related problems
A unified approach to approximating partial covering problems
A tight max-flow min-cut duality theorem for nonlinear multicommodity flows
Approximate max-flow min-multicut theorem for graphs of bounded treewidth
On the dominant of the multicut polytope
Fitting metrics and ultrametrics with minimum disagreements
Primal-dual approximation algorithms for integral flow and multicut in trees
On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
Approximate cut \& packing ratios for multi-commodity arborescences
On the complexity of winner determination and strategic control in conditional approval voting
The B-prize-collecting multicut problem in paths, spider graphs and rings
Minimal multicut and maximal integer multiflow: a survey
The multi-terminal maximum-flow network-interdiction problem
The checkpoint problem
Multiway cuts with a choice of representatives
Approximating maximum integral multiflows on bounded genus graphs
Improved lower bounds on multiflow-multicut gaps
Multi-budgeted directed cuts

This page was built for publication: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

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