Generating pseudo-random permutations and maximum flow algorithms

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

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 languageEnglish (US)
Pages (from-to)201-204
Number of pages4
JournalInformation Processing Letters
Volume35
Issue number4
DOIs
StatePublished - Aug 7 1990
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Generating pseudo-random permutations and maximum flow algorithms'. Together they form a unique fingerprint.

Cite this