Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree |
| |
Authors: | D. B. Johnson P. Metaxas |
| |
Affiliation: | (1) Sudikoff Laboratory for Computer Science, Dartmouth College, 03755-3551 Hanover, NH, USA;(2) Department of Computer Science, Wellesley College, 02181-8289 Wellesley, MA, USA |
| |
Abstract: | The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, EG) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College. |
| |
Keywords: | Optimal parallel and sequential algorithms EREW PRAM model Vertex updating Minimum spanning tree |
本文献已被 SpringerLink 等数据库收录! |
|