Abstract
We describe a simple construction of a family of permutations with a certain pseudo-random property. Such a family can be used to derandomize a recent randomized maximum-flow algorithm of Cheriyan and Hagerup for all relatively dense networks. Hence this supplies a deterministic maximum-flow algorithm that works, on a network with n vertices and m edges, in time O(nm) for all m=Ω(n5/3 log n) (and in time O(nm log n) for all other values of n and m). This improves the running time of the best known deterministic maximum-flow algorithm, due to Goldberg and Tarjan, whose running time is O(nm log(n2/m)).
Original language | English (US) |
---|---|
Pages (from-to) | 201-204 |
Number of pages | 4 |
Journal | Information Processing Letters |
Volume | 35 |
Issue number | 4 |
DOIs | |
State | Published - Aug 7 1990 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Information Systems
- Signal Processing
- Computer Science Applications
Keywords
- Maximum-flow algorithms
- derandomization
- design of algorithms
- longest common ascending subsequence
- pseudo-random permutations