Graph Algorithmic Techniques for Parallel and Distributed Computing

将讨论有关并行和分布式计算的几个主题 研究了 1. 优先图的分配和调度：现有的 超级计算机的并行编译器严重依赖于程序员 运行应用程序。 通过更好地了解 分配和调度问题，这个过程的大部分可以是 自动的 2. 稀疏证书和通信网络：稀疏 图连通性证书（高度连通的跨越 具有相对较少边的子图）已经被引入作为有用的 通信网络的工具。 加权图的证书和 将探讨它们在设计可靠协议中的效用。 这些证书，如果在通信协议中使用得当， 可以节省大量的消息流量 生成的. 3. 图连通性算法：最近的准线性时间 基于拟阵理论的边缘连通性算法将被使用 研究与顶点连通图有关的问题， 和有向图，以及并行连接测试的复杂性 分布式模型。 有效的约简和可并行化 替代方法将被认为是解决这些问题的方法。 问题

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.