A Faster Deterministic Maximum Flow Algorithm

DOI10.1006/jagm.1994.1044zbMath1321.05269OpenAlexW1992170089WikidataQ56018626 ScholiaQ56018626MaRDI QIDQ4314501

No author found.

Publication date: 22 November 1995

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1044

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial games (91A46) Flows in graphs (05C21)

Related Items (31)

Improved balanced flow computation using parametric flow ⋮ A generalization of the scaling max-flow algorithm ⋮ Recent developments in maximum flow algorithms ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Separation, dimension, and facet algorithms for node flow polyhedra ⋮ Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period ⋮ A general approximation method for bicriteria minimization problems ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ Simplifications and speedups of the pseudoflow algorithm ⋮ A note on polynomial algorithm for cost coloring of bipartite graphs with \(\Delta \leq 4\) ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ \(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 ⋮ A fast maximum flow algorithm ⋮ Maximum skew-symmetric flows ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two ⋮ An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem ⋮ Bribery and Control in Stable Marriage ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ A new algorithm for solving the feasibility problem of a network flow ⋮ Clustering with lower-bounded sizes. A general graph-theoretic framework ⋮ Faster algorithms for shortest path and network flow based on graph decomposition ⋮ An improved algorithm for decomposing arc flows into multipath flows

This page was built for publication: A Faster Deterministic Maximum Flow Algorithm