Paper Info
Title
An efficient parallel algorithm for shifting the root of a depth first spanning tree
Abstract
Given a simple, connected, undirected graph G on n vertices and a depth first spanning tree (dfst) T of G with root t, the root-shifting problem is to find a dfst R of G with a specified root r. We present an O(log n) step algorithm for solving this problem using n3 processors on a parallel computer which does not permit concurrent writes but allows concurrent reads. We also discuss a processor allocation strategy for this algorithm which can be implemented without increasing the overall running time of the algorithm.
Year
DOI
Venue
1986
10.1016/0196-6774(86)90040-4
J. Algorithms
Keywords
Field
DocType
efficient parallel algorithm,parallel algorithm,spanning tree
Discrete mathematics,Combinatorics,Minimum degree spanning tree,Prim's algorithm,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Reverse-delete algorithm,Kruskal's algorithm,Minimum spanning tree
Journal
Volume
Issue
ISSN
7
1
0196-6774
Citations 
PageRank 
References 
6
0.71
4
Authors
1
Name
Order
Citations
PageRank
Prasoon Tiwari159296.81