Optimal Parallel Construction of Prescribed Tournaments

Danny Soroker

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-371

, 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-371.pdf

A tournament is a digraph in which every pair of vertices is connected by exactly one arc. The score list of a tournament is the sorted list of the out-degrees of its vertices. Given a non-decreasing sequence of non-negative integers, is it the score list of some tournament? There is a simple test for answering this question. There is also a simple sequential algorithm for constructing a tournament with a given score list. However, this algorithm has a greedy nature, and seems hard to parallelize. We present a simple parallel algorithm for the construction problems. Our algorithm runs in time <i>O</i>(log<i>n</i>) and uses <i>O</i>(<i>n</i>^2/log</i>n</i>) processors on a CREW PRAM, where <i>n</i> is the number of vertices. Since the size of the output is Omega(<i>n</i>^2), our algorithm achieves optimal speedup.

BibTeX citation:

@techreport{Soroker:CSD-87-371,
    Author= {Soroker, Danny},
    Title= {Optimal Parallel Construction of Prescribed Tournaments},
    Year= {1987},
    Month= {Sep},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6225.html},
    Number= {UCB/CSD-87-371},
    Abstract= {A tournament is a digraph in which every pair of vertices is connected by exactly one arc. The score list of a tournament is the sorted list of the out-degrees of its vertices. Given a non-decreasing sequence of non-negative integers, is it the score list of some tournament? There is a simple test for answering this question. There is also a simple sequential algorithm for constructing a tournament with a given score list. However, this algorithm has a greedy nature, and seems hard to parallelize. We present a simple parallel algorithm for the construction problems. Our algorithm runs in time <i>O</i>(log<i>n</i>) and uses <i>O</i>(<i>n</i>^2/log</i>n</i>) processors on a CREW PRAM, where <i>n</i> is the number of vertices. Since the size of the output is Omega(<i>n</i>^2), our algorithm achieves optimal speedup.},
}

EndNote citation:

%0 Report
%A Soroker, Danny 
%T Optimal Parallel Construction of Prescribed Tournaments
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-371
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6225.html
%F Soroker:CSD-87-371