Generating pseudo-random permutations and maximum flow algorithms

DOI10.1016/0020-0190(90)90024-RMaRDI QIDQ915489zbMATH OpenFDO

Authors Noga Alon

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

derandomizationdesign of algorithmspseudo-random permutationslongest common ascending subsequencerandomized maximum-flow algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• A Randomized Maximum-Flow Algorithm
• An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
• scientific article; zbMATH DE number 742960
• scientific article; zbMATH DE number 177817
• Probabilistic Analysis of Network Flow Algorithms

Cites work

• A Fast and Simple Algorithm for the Maximum Flow Problem
• A data structure for dynamic trees
• A new approach to the maximum-flow problem
• Improved Time Bounds for the Maximum Flow Problem
• Scaling algorithms for network problems

Cited in

(10)

• Fast generation of random permutations via networks simulation
• Search for all \(d\)-mincuts of a limited-flow network
• Quasirandom arithmetic permutations
• A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
• Capacity expansion and reliability evaluation on the networks flows with continuous stochastic functional capacity
• Quasirandom permutations
• On Compatible Matchings
• Computational investigations of maximum flow algorithms
• Constructions of permutation arrays for certain scheduling cost measures
• Recent developments in maximum flow algorithms

This page was built for publication: Generating pseudo-random permutations and maximum flow algorithms

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