Simple parallel algorithms for the replacement edge problem and related problems on minimum spanning trees
Authors:Jyrki Katajainen and Jesper Larsson Träff
Published in:Proceedings of the 18th Australasian Computer Science Conference, Australian Computer Science Communications 17,1, (1995), 254-261
Full text:<pdf.gif>PDF (141 kB)  <ps.gif>PS (244 kB)  
Abstract:Let G be a connected, undirected, and weighted graph with n vertices and m edges. Further, let S be a spanning tree of G and T a minimum spanning tree of G. In this paper we present parallel algorithms for solving the following problems:
(a) 
Given G and T, for each edge e of T, determine a replacement edge f by which e should be replaced to create a new minimum spanning tree if e is removed from G.
(b) 
Given G and T, find a most vital edge of G with respect to T, that is, an edge whose removal has the largest impact on the weight of T.
(c) 
Given G and S, determine whether S is a minimum spanning tree.
(d) 
Given G and T, compute, for each edge e of G, by how much the weight of e can change without affecting the minimality of T.
The algorithms run in O(logn) time and O(m) space with m processors. The problems (a), (b), and (d) are solved on a MINIMUM CRCW PRAM, whereas the problem (c) is solved on a CREW PRAM. The algorithms utilizes a simple technique for computing functions defined on paths in rooted trees that might be of independent interest.
BibLATEX:
@inproceedings{KT1995C,
  author = {Jyrki Katajainen and Jesper Larsson Tr\"{a}ff},
  title = {Simple parallel algorithms for the replacement edge problem and
    related problems on minimum spanning trees},
  booktitle = {Proceedings of the 18th Australasian Computer Science
    Conference},
  series = {Australian Computer Science Communications},
  volume = {17},
  number = {1},
  year = {1995},
  pages = {254--261},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.