Fast Parallel Algorithms for Graphs and Networks
Abstract
Many theorems in graph theory give simple characterizations for testing the existence of objects with certain properties, which can be translated into fast parallel algorithms. However, transforming these tests into algorithms for constructing such objects is often a real challenge. In this thesis we develop fast parallel (NC) algorithms for several such construction problems. The first part is about tournaments. (A tournament is a digraph in which there is precisely one arc between every two vertices.) Two classical results state that every tournament has a Hamiltonian path and every strongly connected tournament has a Hamiltonian cycle. We derive efficient parallel algorithms for finding these objects. Our algorithms yield new proofs of these theorems. In solving the cycle problem we also solve the problem of finding a Hamiltonian path with one fixed endpoint. Next we address the problem of constructing a tournament with a specified degree-sequence, and give an NC algorithm for it which achieves optimal speedup. The second part is concerned with making graphs strongly connected via orientation and augmentation. A graph is strongly orientable if its edges can be assigned orientations to yield a strongly connected digraph. Robbins' theorem states the conditions for a graph to be strongly orientable. His theorem was generalized for mixed graphs, i.e. ones that have both directed and undirected edges. We give a fast parallel algorithm for strongly orienting mixed graphs. We then solve the problem of adding a minimum number of arcs to a mixed graph to make it strongly orientable. This problem was not previously known to have even a polynomial time sequential solution \201a sequential algorithm was discovered independently by Gusfield\202. In the process of solving the general problem we derive solutions for the special cases of undirected graphs. The final part of the thesis describes a methodology which yields deterministic parallel algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1987
- Accession Number
- ADA619427
Entities
People
- Danny Soroker
Organizations
- University of California, Berkeley