Parallel Computations in Graph Theory

In parallel computation two approaches are common; namely unbounded parallelism and bounded parallelism. In this paper both approaches will be considered. The problem of unbounded parallelism is studied in section II and some lower and upper bounds on different connectivity problems for directed and undirected graphs are presented. In section III we mention bounded parallelism and three different k-parallel graph search techniques, namely k-depth search, breadth depth search, and breadth-first search. Each algorithm is analyzed with respect to the optimal serial algorithm. It is shown that for sufficiently dense graphs the parallel breadth first search technique is very close to the optimal bound. Techniques for searching sparse graphs are also discussed.

Authors

• Eshrat Arjomandi
• Derek G. Corneil

Keywords

• Concurrent computing
• Graph theory
• Parallel processing
• Upper bound
• Arithmetic
• Algorithm design and analysis
• Computer science
• Performance evaluation
• Testing
• Tree graphs
• Parallelization
• Unit Time
• Undirected
• Shortest Path
• Directed Graph
• First Search
• Sequential Algorithm
• Pattern Search
• Parallel Algorithm
• Depth-first
• Breadth-first Search
• Algorithm In This Paper
• Sparse Graph
• Graph Algorithms
• Graph Of Order
• Class Of Graphs
• Vector C
• Start Node
• Weak Component
• Balanced Tree
• Boolean Matrix
• Reduction Factor
• Number Of Processors
• Weak Connections