|
 |
english only
PARADIAM: Parallel Computation of the Diameter of a Graph
WARNING: this stuff is fairly old...
The diameter of a graph is the maximum length of shortest paths between two vertices in the graph. For most regular graphs, it is a function of the number of nodes in the graph, but in general its value has to be computed. If the graph is large, this might require powerful computing facilities and parallelism is here to help.
The codes are available here. I have had reports that the code crashes on non-connected graphs. Our results appear in:
- J.-A. Ferrez, K. Fukuda, Th.M. Liebling, Parallel implementation of graph diameter algorithms, EPFL Supercomputing Review, No 10, nov 1998.
- J.-A. Ferrez, K. Fukuda, Th.M. Liebling, Parallel computation of the diameter of a graph, in High Performance Computing Systems and Applications, J. Schaeffer ed., Kluwer Academic Publishers, 283-296, 1998.
The parallel environment
We have used several platforms to develop and run our programs:
- A CRAY T3D with 256 PEs, with the shmem library.
- An SGI Origin2000 with 32 PEs, with the MIPSPro parallel compiler (shared memory multi-threading) and with MPI.
- The Swiss-T0 prototype, 8 DEC Alpha nodes, with MPI.
- A cluster of 20 SGI O2 workstations, with MPI.
- A dual Pentium II PC running Linux, with MPI and multithreading.
Web resources
Some people involved and their publications
Web search engines
Online tutorials
- Parallel Programming with Maisie.
- The Degree/Diameter Problem.
- Case Study: Shortest-Path Algorithms as part of Designing and Building Parallel Programs by Ian Foster.
- Chapters of the Prototype Electronic Textbook : APSP 1 and APSP 2.
Codes
- Dijkstra's Shortest Path Algorithm Animation in Java : If you do not understand very well how Dijkstra's algorithm work, this is for you !
- Code from Discrete Optimization Algorithms with Pascal Programs by Maciej M. Syslo, Narsingh Deo, and Janusz S. Kowalik
|
©2002 ROSO-EPFL, 1015 Lausanne, Jean-Albert Ferrez update: 27 October 2002 |