Maximum flow and minimum-cost flow in almost-linear time
From MaRDI portal
Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Convex programming (90C25) Programming involving graphs or networks (90C35) Interior-point methods (90C51)
Cites work
- 2-norm flow diffusion in near-linear time
- A combinatorial cut-toggling algorithm for solving Laplacian linear systems
- A combinatorial interior point method for network flow problems
- A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem
- A data structure for dynamic trees
- A deterministic almost-linear time algorithm for minimum-cost flow
- A fast maximum flow algorithm
- A Faster Strongly Polynomial Minimum Cost Flow Algorithm
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- A new approach to the maximum-flow problem
- A new polynomial-time algorithm for linear programming
- A polynomial time primal network simplex algorithm for minimum cost flows
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
- A strongly polynomial minimum cost circulation algorithm
- A tale of three eras: the discovery and rediscovery of the Hungarian method
- A theory of alternating paths and blossoms from the perspective of minimum length
- Algorithms for the minimum cost circulation problem based on maximizing the mean improvement
- An O (n 2 (m + N log n )log n ) min-cost flow algorithm
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An \(O(EV\log^2V)\) algorithm for the maximal flow problem
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
- An Out-of-Kilter Method for Minimal-Cost Flow Problems
- Approximate Gomory–Hu tree is faster than n – 1 max-flows
- Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
- Area-convexity, _ regularization, and undirected multicommodity flow
- Beyond the flow decomposition barrier
- Bipartite matching in nearly-linear time on moderately dense graphs
- Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time
- Canceling most helpful total cuts for minimum cost network flow
- Circulation control for faster minimum cost flow in unit-capacity graphs
- Computing maximum flow with augmenting electrical flows
- Decremental all-pairs shortest paths in deterministic near-linear time
- Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing
- Deterministic decremental SSSP and approximate min-cost flow in almost-linear time
- Deterministic min-cut in poly-logarithmic max-flows
- Dynamic Maxflow via Dynamic Interior Point Methods
- Dynamic minimum spanning forest with subpolynomial worst-case update time
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Expander decomposition and pruning: faster, stronger, and simpler
- Fast approximation algorithms for cut-based problems in undirected graphs
- Fast dynamic cuts, distances and effective resistances via vertex sparsifiers
- Faster p-norm minimizing flows, via smoothed q-norm problems
- Faster and more dynamic maximum flow by incremental breadth-first search
- Faster approximate multicommodity flow using quadratically coupled flows
- Faster energy maximization for faster maximum flow
- Faster maxflow via improved dynamic spectral vertex sparsifiers
- Faster scaling algorithms for general graph matching problems
- Faster Scaling Algorithms for Network Problems
- Faster sparse minimum cost flow by electrical flow localization
- Finding minimum-cost circulations by canceling negative cycles
- Finding minimum-cost flows by double scaling
- Flows in almost linear time via adaptive preconditioning
- Fully dynamic electrical flows: sparse maxflow faster than Goldberg-Rao
- Fully-dynamic graph sparsifiers against an adaptive adversary
- Graph partitioning using single commodity flows
- scientific article; zbMATH DE number 5485537 (Why is no real title available?)
- scientific article; zbMATH DE number 5485557 (Why is no real title available?)
- scientific article; zbMATH DE number 487935 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- scientific article; zbMATH DE number 3069634 (Why is no real title available?)
- scientific article; zbMATH DE number 7788485 (Why is no real title available?)
- Incremental approximate maximum flow on undirected graphs in subpolynomial update time
- Introductory lectures on convex optimization. A basic course.
- Isotonic regression via partitioning
- Iterative Bregman projections for regularized transportation problems
- Iterative refinement for \(\ell_p\)-norm regression
- Local flow partitioning for faster edge connectivity
- Matching algorithms are fast in sparse random graphs
- Matching theory
- Matrix scaling and balancing via box constrained Newton's method and interior point methods
- Maximum matchings in general graphs through randomization
- Maximum skew-symmetric flows and matchings
- Minimizing a Convex Cost Closure Set
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Minimum cuts in directed graphs via partial sparsification
- Minimum-cost flow algorithms: an experimental evaluation
- Much faster algorithms for matrix scaling
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Navigating central path with electrical flows: from flows to matchings, and back
- Nearly maximum flows in nearly linear time
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
- Network Flow and Testing Graph Connectivity
- Optimal vertex connectivity oracles
- Paths, Trees, and Flowers
- Polynomial dual network simplex algorithms
- Scaling algorithms for network problems
- Scaling Algorithms for the Shortest Paths Problem
- Scaling algorithms for weighted matching in general graphs
- Solving Linear Programs in the Current Matrix Multiplication Time
- Solving tall dense linear programs in nearly linear time
- The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
- The Partial Augment–Relabel Algorithm for the Maximum Flow Problem
- The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
- The weighted matching approach to maximum cardinality matching
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- Unit capacity maxflow in almost \(O(m^{4/3})\) time
- Universal Barrier Is n-Self-Concordant
- Using petal-decompositions to build a low stretch spanning tree
- Vertex connectivity in poly-logarithmic max-flows
Cited in
(4)
This page was built for publication: Maximum flow and minimum-cost flow in almost-linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6939379)
