A Randomized Maximum-Flow Algorithm

DOI10.1137/S0097539791221529zbMATH Open0827.68049MaRDI QIDQ4834375FDOQ4834375

Authors: Torben Hagerup, Joseph Cheriyan 

Publication date: 30 May 1995

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• A Faster Deterministic Maximum Flow Algorithm
• scientific article; zbMATH DE number 177817
• An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• A new approach to the maximum-flow problem

zbMATH Keywords

randomized algorithmmaximum flowFibonacci heap

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10)

Cited In (9)

• A Faster Deterministic Maximum Flow Algorithm
• Improved balanced flow computation using parametric flow
• Maximum likelihood analysis of the Ford-Fulkerson method on special graphs
• Probabilistic Analysis of Network Flow Algorithms
• Separation, dimension, and facet algorithms for node flow polyhedra
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating pseudo-random permutations and maximum flow algorithms
• Recent developments in maximum flow algorithms

This page was built for publication: A Randomized Maximum-Flow Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4834375)