Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
From MaRDI portal
Publication:3158558
Recommendations
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Approximate max-integral-flow/min-multicut theorems
- Improved bounds on the max-flow min-cut ratio for multicommodity flows
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Computing and Combinatorics
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Approximation and Online Algorithms
- Minimal multicut and maximal integer multiflow: a survey
Cited in
(only showing first 100 items - show all)- Routing in undirected graphs with constant congestion
- Multicommodity network flows: a survey. I: Applications and formulations
- On the cover time of dense graphs
- Separators in region intersection graphs
- Iterated multilevel simulated annealing for large-scale graph conductance minimization
- Cutwidth: obstructions and algorithmic aspects
- Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
- A note on multiflows and treewidth
- Linear time algorithms for finding sparsest cuts in various graph classes
- Single-Sink Multicommodity Flow with Side Constraints
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Correlation clustering in general weighted graphs
- Most balanced minimum cuts
- On the complexity of finding balanced oneway cuts
- Designing multi-commodity flow trees
- Congestion-free rerouting of flows on DAGs
- \(d\)-dimensional arrangement revisited
- A decentralized algorithm for spectral analysis
- Minimal multicut and maximal integer multiflow: a survey
- A simple algorithm for the multiway cut problem
- Bounds on maximum concurrent flow in random bipartite graphs
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Approximate duality of multicommodity multiroute flows and cuts: single source case
- Rerouting Flows when Links Fail
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- Electric routing and concurrent flow cutting
- A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES
- Inoculation strategies for victims of viruses and the sum-of-squares partition problem
- Approximating the rectilinear crossing number
- Braess's paradox in expanders
- The complexity status of problems related to sparsest cuts
- Approximation algorithms for treewidth
- Hallucination helps: energy efficient virtual circuit routing
- Single-commodity robust network design with finite and hose demand sets
- Euclidean distortion and the sparsest cut
- Approximation algorithms for the weighted t-uniform sparsest cut and some other graph partitioning problems
- Network coding in undirected graphs is either very helpful or not helpful at all
- On the Max-flow min-cut ratio for directed multicommodity flows
- Max-flow min-cut theorem in quantum computing
- The small set vertex expansion problem
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Simplex partitioning via exponential clocks and the multiway-cut problem
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- Algorithms for the universal and a priori TSP
- On the Parameterized Complexity of Clique Elimination Distance
- Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Flow metrics
- Approximating the rectilinear crossing number
- Vertical perimeter versus horizontal perimeter
- On algorithms employing treewidth for \(L\)-bounded cut problems
- Simulation-based system reliability estimation of a multi-state flow network for all possible demand levels
- Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
- Constant congestion routing of symmetric demands in planar directed graphs
- The complexity of finding uniform sparsest cuts in various graph classes
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Feedback arc set problem in bipartite tournaments
- Crossing number, pair-crossing number, and expansion
- Graph Clustering in All Parameter Regimes
- Shift of pairwise similarities for data clustering
- Grid spanners with low forwarding index for energy efficient networks
- Structural routability of \(n\)-pairs information networks
- Pathwidth, trees, and random embeddings
- Fast approximation algorithms for multicommodity flow problems
- Approximation algorithms for requirement cut on graphs
- EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
- On certain connectivity properties of the internet topology
- Approximation algorithms for Euler genus and related problems
- The multi-multiway cut problem
- Optimal nonparametric testing of missing completely at random and its connections to compatibility
- A separator theorem for string graphs and its applications
- Stochastic embeddings of graphs into trees
- \(\ell ^2_2\) spreading metrics for vertex ordering problems
- Multicommodity flow approximation used for exact graph partitioning
- Advances in metric embedding theory
- Near-optimal separators in string graphs
- Terminal embeddings
- New algorithms for maximum disjoint paths based on tree-likeness
- scientific article; zbMATH DE number 7378699 (Why is no real title available?)
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Euclidean prize-collecting Steiner forest
- Minimum fill-in: inapproximability and almost tight lower bounds
- Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
- The all-or-nothing flow problem in directed graphs with symmetric demand pairs
- Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem
- A polyhedral study of lifted multicuts
- Approximation algorithms for digraph width parameters
- Partitioning well-clustered graphs: spectral clustering works!
- \(N\)-fold integer programming and nonlinear multi-transshipment
- Approximating small balanced vertex separators in almost linear time
- Lattice flows in networks
- Sparsest cuts and concurrent flows in product graphs.
- Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- General variable neighborhood search for computing graph separators
- Communities, Random Walks, and Social Sybil Defense
- Approximating Requirement Cut via a Configuration LP
- Cut-sufficient directed 2-commodity multiflow topologies
- Structure of graphs with locally restricted crossings
- On cutwidth parameterized by vertex cover
- Approximation algorithms via contraction decomposition
This page was built for publication: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158558)
