Max flows in O(nm) time, or better

From MaRDI portal
Publication:5495847

DOI10.1145/2488608.2488705zbMath1293.05151OpenAlexW1983383464WikidataQ56018629 ScholiaQ56018629MaRDI QIDQ5495847

James B. Orlin

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




Related Items (99)

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining ExtendedFlow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and PerformanceTwo-level rectilinear Steiner treesMinimum Cuts in Surface GraphsImproved balanced flow computation using parametric flowHierarchical \(b\)-matchingMaximum likelihood analysis of the Ford-Fulkerson method on special graphsIntegrating security constraints into fixed priority real-time schedulersOn a general framework for network representability in discrete optimizationA compact representation for minimizers of \(k\)-submodular functionsFinding Two Edge-Disjoint Paths with Length ConstraintsRobust scheduling of wireless sensor networks for target tracking under uncertaintyScheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time periodMinimum parametric flow in time-dependent dynamic networksUnit Capacity Maxflow in Almost $m^{4/3}$ TimeComputing Weighted Strength and Applications to PartitioningMinimum Cuts and Sparsification in HypergraphsA primal-dual approximation algorithm for \textsc{minsat}A general approximation method for bicriteria minimization problemsEnhanced instance space analysis for the maximum flow problemA note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\)Dynamic network flow location models and algorithms for quickest evacuation planningFinding dense subgraphs with maximum weighted triangle densityA faster strongly polynomial time algorithm to solve the minimum cost tension problemHypergraph Cuts with General Splitting FunctionsA sequential Stackelberg game for dynamic inspection problemsA linear-time parameterized algorithm for computing the width of a DAGSubmodular reassignment problem for reallocating agents to tasks with synergy effectsUsing the minimum maximum flow degree to approximate the flow coloring problemMultiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time\(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphsTight Localizations of Feedback SetsHow vulnerable is an undirected planar graph with respect to max flowMaximum flows in parametric graph templatesBroadcasting in split graphsFinding Maximum Edge-Disjoint Paths Between Multiple TerminalsA fast maximum flow algorithmBudget-feasible mechanisms for proportionally selecting agents from groupsStable marriage with groups of similar agentsReLU neural networks of polynomial size for exact maximum flow computationTemporal flows in temporal networksA survey on exact algorithms for the maximum flow and minimum‐cost flow problemsExplicit Baranyai partitions for quadruples, Part I: Quadrupling constructionsGeneralizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniquesHow vulnerable is an undirected planar graph with respect to max flowMinimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest PathsUnnamed ItemPartial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-normSolving hard stable matching problems involving groups of similar agentsGraphs with no \(K_{3,3}\) minor containing a fixed edgeA Strongly Polynomial Algorithm for Generalized Flow MaximizationEnumerating \(k\)-arc-connected orientationsUnnamed ItemUnnamed ItemUnnamed ItemFirst-order dominance: stronger characterization and a bivariate checking algorithmEfficient computation of tolerances in the weighted independent set problem for some classes of graphsParsimonious formulations for low-diameter clustersCounting and sampling minimum cuts in genus \(g\) graphsAlgorithms and bounds for drawing directed graphsA polynomial time algorithm for the minimum flow problem in time-varying networksThe Optimal Design of Low-Latency Virtual BackbonesA parameterized algorithmics framework for degree sequence completion problems in directed graphsEfficient and Adaptive Parameterized Algorithms on Modular DecompositionsOn the complexity of the flow coloring problemThe complexity of routing with collision avoidanceBribery and Control in Stable MarriageInverse maximum flow problem under the combination of the weighted \(l_2\) norm and the weighted Hamming distanceParametric multiroute flow and its application to multilink-attack networkBlocking unions of arborescencesExact solution of hub network design problems with profitsInterval scheduling maximizing minimum coverageApproximate Nash equilibria in anonymous gamesFaster balanced clusterings in high dimensionUnnamed ItemInverse minimum flow problem under the weighted sum-type Hamming distanceClustering with lower-bounded sizes. A general graph-theoretic frameworkCapacitated partial inverse maximum spanning tree under the weighted Hamming distanceGraph orientation with splitsApproximating \(k\)-forest with resource augmentation: a primal-dual approachParameterized complexity of length-bounded cuts and multicutsSubset feedback vertex set on graphs of bounded independent set sizeAvoidable vertices and edges in graphs: existence, characterization, and applicationsA New Framework for Hierarchical DrawingsOn a General Framework for Network Representability in Discrete OptimizationA Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract)Separators and adjustment sets in causal graphs: complete criteria and an algorithmic frameworkUnnamed ItemFaster algorithms for shortest path and network flow based on graph decompositionAn approximation algorithm for a general class of multi-parametric optimization problemsTwo edge-disjoint paths with length constraintsLinear-size hopsets with small hopbound, and constant-hopbound hopsets in RNCComputing the 2-blocks of directed graphsComputing the \(k\) densest subgraphs of a graphUnnamed ItemAlgorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factorsGraph Orientation with Edge ModificationsLexicographic optimal homologous chains and applications to point cloud triangulationsDegree-constrained graph orientation: maximum satisfaction and minimum violation




This page was built for publication: Max flows in O(nm) time, or better