Graph Algorithmic Techniques for Parallel and Distributed Computing

点击翻译按钮获取中文摘要

Several topics concerning parallel and distributed computing will be investigated. 1. Assignment and Scheduling of Precedence Graphs: The existing parallel compilers for supercomputers rely heavily on the programmer for running an application. By gaining a better understanding of assignment and scheduling issues, much of this process can be automated. 2. Sparse Certificates and Communication Networks: Sparse certificates for graph connectivity (highly connected spanning subgraphs with relatively few edges) have been introduced as a useful tool for communication networks. Certificates for weighted graphs and their utility in the design of reliable protocols will be explored. These certificates, if employed properly in communication protocols, could result in considerable savings in the amount of message traffic generated. 3. Algorithms for Graph Connectivity: A recent almost-linear time algorithm for edge connectivity based on matroid theory will be used to investigate questions pertaining to the vertex connectivity graphs and digraphs, and the complexity of connectivity testing on parallel and distributed models. Efficient reductions and parallelizable alternate methods will be considered as ways of solving these problems.