๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The average-case parallel complexity of sorting

โœ Scribed by Ravi B. Boppana

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
219 KB
Volume
33
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Upper and lower bounds for the average-c
Upper and lower bounds for the average-case complexity of path-search
โœ Pippenger, Nicholas ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 125 KB ๐Ÿ‘ 1 views

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting ent

Average-case complexity of shortest-path
Average-case complexity of shortest-paths problems in the vertex-potential model
โœ Colin Cooper; Alan Frieze; Kurt Mehlhorn; Volker Priebe ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 146 KB ๐Ÿ‘ 2 views

We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and wit