Fast Parallel Algorithms for Graphs and Networks

Danny Soroker

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-390

, 1987

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

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 (a sequential algorithm was discovered independently by Gusfield). 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 for several supply-demand problems on networks with zero-one capacities. These problems include: constructing a zero-one matrix with specified row- and column-sums, constructing a simple digraph with specified in- and out-degrees and constructing a zero-one flow pattern in a complete network, where each vertex has a specified net supply or demand. We extend our results to the case where the input represents upper bounds on supplies and lower bounds on demands.

Advisors: Richard M. Karp

BibTeX citation:

@phdthesis{Soroker:CSD-87-390,
Author= {Soroker, Danny},
Title= {Fast Parallel Algorithms for Graphs and Networks},
School= {EECS Department, University of California, Berkeley},
Year= {1987},
Month= {Dec},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5852.html},
Number= {UCB/CSD-87-390},
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 (a sequential algorithm was discovered independently by Gusfield). 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 for several supply-demand problems on networks with zero-one capacities. These problems include: constructing a zero-one matrix with specified row- and column-sums, constructing a simple digraph with specified in- and out-degrees and constructing a zero-one flow pattern in a complete network, where each vertex has a specified net supply or demand. We extend our results to the case where the input represents upper bounds on supplies and lower bounds on demands.},
}

EndNote citation:

%0 Thesis
%A Soroker, Danny 
%T Fast Parallel Algorithms for Graphs and Networks
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-390
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5852.html
%F Soroker:CSD-87-390