TY - GEN
T1 - O(1) parallel time incremental graph algorithms
AU - Sherlekar, Deepak D.
AU - Pawagi, Shaunak
AU - Ramakrishnan, I. V.
N1 - Publisher Copyright:
© 1985, Springer-Verlag.
PY - 1985
Y1 - 1985
N2 - Fast parallel algorithms are presented for updating minimum spanning trees, connected components and bridges of an undirected graph when a minor change is made to the graph such as addition or deletion of a vertex or an edge. The machine model used is a parallel random access machine that allows simultaneous reads as well as simultaneous writes into the same memory location. In the latter case one processor succeeds but we do not know which. The algorithms described in this paper require O(1) time and are efficient when compared to previously known O(logn) time algorithms for initial computation of the above mentioned graph properties on this model. An important feature of our algorithms is their versatility, that is, they can be adapted to run efficiently on all variations of this model with very little modification.
AB - Fast parallel algorithms are presented for updating minimum spanning trees, connected components and bridges of an undirected graph when a minor change is made to the graph such as addition or deletion of a vertex or an edge. The machine model used is a parallel random access machine that allows simultaneous reads as well as simultaneous writes into the same memory location. In the latter case one processor succeeds but we do not know which. The algorithms described in this paper require O(1) time and are efficient when compared to previously known O(logn) time algorithms for initial computation of the above mentioned graph properties on this model. An important feature of our algorithms is their versatility, that is, they can be adapted to run efficiently on all variations of this model with very little modification.
UR - https://www.scopus.com/pages/publications/85027882690
U2 - 10.1007/3-540-16042-6_27
DO - 10.1007/3-540-16042-6_27
M3 - Conference contribution
AN - SCOPUS:85027882690
SN - 9783540160427
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 477
EP - 495
BT - Foundations of Software Technology and Theoretical Computer Science - 5th Conference, Proceedings
A2 - Maheshwari, S.N.
PB - Springer Verlag
T2 - 5th Conferences on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1985
Y2 - 16 December 1985 through 18 December 1985
ER -