STOC Conference 1981 Conference Paper
A Difference in Efficiency between Synchronous and Asynchronous Systems
- Eshrat Arjomandi
- Michael J. Fischer
- Nancy A. Lynch
Author name cluster
Eshrat Arjomandi
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2FOCS Conference 1975 Conference Paper
Parallel Computations in Graph Theory
- Eshrat Arjomandi
- Derek G. Corneil
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.