Optimal Parallel Construction of Prescribed Tournaments

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 O(log n) and uses O(n(2)/logn) processors on a CREW PRAM, where n is the number of vertices. Since the size of the output is Theta(n(2), our algorithm achieves optimal speedup.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1987
Accession Number
ADA603999

Entities

People

  • Danny Soroker

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • California
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Electrical Engineering
  • Engineering
  • Graph Theory
  • Graphs
  • Information Operations
  • Mathematics
  • Naval Warfare
  • Sequences
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.