Max flows in O(nm) time, or better
From MaRDI portal
Publication:5495847
DOI10.1145/2488608.2488705zbMath1293.05151DBLPconf/stoc/Orlin13OpenAlexW1983383464WikidataQ56018629 ScholiaQ56018629MaRDI QIDQ5495847
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2488608.2488705
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)
Related Items (99)
Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended ⋮ Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Two-level rectilinear Steiner trees ⋮ Minimum Cuts in Surface Graphs ⋮ Improved balanced flow computation using parametric flow ⋮ Hierarchical \(b\)-matching ⋮ Maximum likelihood analysis of the Ford-Fulkerson method on special graphs ⋮ Integrating security constraints into fixed priority real-time schedulers ⋮ On a general framework for network representability in discrete optimization ⋮ A compact representation for minimizers of \(k\)-submodular functions ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Robust scheduling of wireless sensor networks for target tracking under uncertainty ⋮ Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period ⋮ Minimum parametric flow in time-dependent dynamic networks ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ A general approximation method for bicriteria minimization problems ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ A note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\) ⋮ Dynamic network flow location models and algorithms for quickest evacuation planning ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ A faster strongly polynomial time algorithm to solve the minimum cost tension problem ⋮ Hypergraph Cuts with General Splitting Functions ⋮ A sequential Stackelberg game for dynamic inspection problems ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Submodular reassignment problem for reallocating agents to tasks with synergy effects ⋮ Using the minimum maximum flow degree to approximate the flow coloring problem ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Tight Localizations of Feedback Sets ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Maximum flows in parametric graph templates ⋮ Broadcasting in split graphs ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ A fast maximum flow algorithm ⋮ Budget-feasible mechanisms for proportionally selecting agents from groups ⋮ Stable marriage with groups of similar agents ⋮ ReLU neural networks of polynomial size for exact maximum flow computation ⋮ Temporal flows in temporal networks ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Explicit Baranyai partitions for quadruples, Part I: Quadrupling constructions ⋮ Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Graphs with no \(K_{3,3}\) minor containing a fixed edge ⋮ A Strongly Polynomial Algorithm for Generalized Flow Maximization ⋮ Enumerating \(k\)-arc-connected orientations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ First-order dominance: stronger characterization and a bivariate checking algorithm ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ Parsimonious formulations for low-diameter clusters ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Algorithms and bounds for drawing directed graphs ⋮ A polynomial time algorithm for the minimum flow problem in time-varying networks ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ On the complexity of the flow coloring problem ⋮ The complexity of routing with collision avoidance ⋮ Bribery and Control in Stable Marriage ⋮ Inverse maximum flow problem under the combination of the weighted \(l_2\) norm and the weighted Hamming distance ⋮ Parametric multiroute flow and its application to multilink-attack network ⋮ Blocking unions of arborescences ⋮ Exact solution of hub network design problems with profits ⋮ Interval scheduling maximizing minimum coverage ⋮ Approximate Nash equilibria in anonymous games ⋮ Faster balanced clusterings in high dimension ⋮ Unnamed Item ⋮ Inverse minimum flow problem under the weighted sum-type Hamming distance ⋮ Clustering with lower-bounded sizes. A general graph-theoretic framework ⋮ Capacitated partial inverse maximum spanning tree under the weighted Hamming distance ⋮ Graph orientation with splits ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ A New Framework for Hierarchical Drawings ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract) ⋮ Separators and adjustment sets in causal graphs: complete criteria and an algorithmic framework ⋮ Unnamed Item ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ An approximation algorithm for a general class of multi-parametric optimization problems ⋮ Two edge-disjoint paths with length constraints ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Computing the 2-blocks of directed graphs ⋮ Computing the \(k\) densest subgraphs of a graph ⋮ Unnamed Item ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ Graph Orientation with Edge Modifications ⋮ Lexicographic optimal homologous chains and applications to point cloud triangulations ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation
This page was built for publication: Max flows in O(nm) time, or better
