G. The weight of a spanning tree is the sum of the weights of the edges belonging to that tree. A minimum spanning tree, TG is a spanning tree of G whose weight is a minimum.

There are occasions when we have to add or delete edges from the graph under consideration. This may be due to the addition of new links or existing links going out of service in a network. We use the notation G-? to denote the graph G? = (V, E-?) where ? is a subset of the set of edges E. In particular, G-e denotes the graph resulting from deleting the edge e (? E). Similarly, G+e denotes the result of adding the edge e to the graph G.

The most vital edge (MVE) problem may now be defined as follows. Let g(G) denote the weight of a minimum spanning tree of G if G is connected; g(G) = ? if the graph is not connected. If g(G-e) ? g(G-e?) for every edge e? in G then the edge e is said to be a most vital edge in G. Finding such an edge e is referred to as the MVE problem (see Hsu et al. [5]).

The remainder of this paper is organized as follows. In Section 2 we give the preliminaries required for the paper. Some known results related to the minimum spanning tree problem and the MVE problem are also given. In Section 3 we present the main result of this paper, that is, the parallel MVE algorithm. An example is given to show the working of this algorithm. In Section 4 we present the complexity analysis for the algorithm. Finally, in Section 5 we present the concluding remarks.

1. Introduction

In this paper we present a parallel algorithm for the most vital edge problem. For this problem there are sequential/parallel algorithms such as Hsu et al. [5,6]. The complexities of these algorithms are O(p2) and O(qlogq) where p, q are the number of vertices and edges respectively of the graph. Recently, Lin and Chern gave an NP-hard version for the same problem, see for example [7]. When designing a network the designer may wish to know which of the edges are valuable to the network. Finding which edge is the most vital one is referred to as the most vital edge (MVE) problem. The uses of minimum spanning trees are well known in application areas like operations research, engineering, VLSI design, data communication networks, image processing, etc. In the construction of minimum spanning trees sometimes it is useful to know the most vital edge of the network.

For reasons of standardization, we shall assume that the reader is familiar with rudimentary graph theoretic terminology as in [1,10]. The input is an undirected, weighted graph G = (V, E) with n = |V| vertices and m = |E| edges. The vertices and edges are sometimes referred to as the nodes and links, respectively. A graph is said to be weighted if there is a positive weight w(e) associated with every edge e in E. The weight of an edge may be thought of as its length or the cost of laying a cable between the two end vertices of the edge. A spanning tree of G is a tree connecting all the vertices of the graph

An O(log m) parallel algorithm for the most vital edge

problem

Francis Suraweera and Piyush Maheshwari School of Computing and Information Technology, Griffith University, Brisbane, Qld. 4111, Australia

Abstract: In this paper we study a parallel algorithm for the computation of the most vital edge (MVE) problem with respect to a given minimum spanning tree. Our algorithm runs on O(m) processors and has running time of O(log m), where m is the number of edges and n is the number of vertices of the given graph.

Keywords: Parallel algorithms, graph algorithms, complexity, minimum spanning tree, most vital edge problem.