| ||||||||||
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.
2. Preliminaries
Here we collect some of the known results on the characteristics of the minimum spanning trees and the MVE problem. These will be stated in the form of lemmas without proofs, and wherever possible, we will give references to the original sources. The following design criteria have been used by different MST algorithms, see for example Graham and Hell [4].
1. Add a shortest edge which joins different fragments.
2. Choose a vertex, v arbitrarily. Add a shortest edge which joins the fragment containing v to another fragment.
3. For every fragment add the shortest edge which joins it to another fragment.
By far the most popular form of the design criterion is the following lemma, which is known as the MST property [2, p. 234].
Lemma 1. Let G = (V, E) be a connected, undirected weighted graph. Let U ? V. Let the edge (u, v) ? E be a lowest weight edge such that u ? U and v ? V-U. Then there is a minimum spanning tree that contains (u, v) as an edge.
Lemma 2. If e is a bridge of the graph G then e must be in the MST. (This is true by definition).
The next set of lemmas use the following definitions and notations.
TG: the minimum spanning tree of graph G;
W: the set of edges belonging to the minimum spanning tree, TG; for simplicity we shall call these edges the tree-edges.
f(e): this is the entering edge corresponding to the leaving edge e belonging to W. It should be noted that f(e) belongs to E-W and f(e) forms a tree edge in TG-e.
Lemma 3. Let TG be a minimum spanning tree of G. The most vital edge e of G is one of the edges in TG.
Lemma 4. If e is in W then TG-e = TG - e + f(e). Hence, w(TG-e) = w(TG) - w(e) + w(f(e)) where W is the set of tree-edges, e is the leaving edge,
and f(e) replaces the edge e to form the new MST, TG-e.
Lemma 5. Let f(e) be the edge that replaces the edge e in W. Then w(f(e)) - w(e) ? 0.
Remark: The equality is possible when the edge weights are not distinct. The Lemmas 3 and 4 above are directly from Hsu et al. [5].
3. Parallel algorithm for MVE problem
We are now ready to state the main result of this section. But first we digress and give below a procedure for constructing minimum spanning trees. To make the paper self-contained we reproduce this procedure here. For further details please see [8]. A brief illustration of working of our main algorithm is given in Figures 2 and 3. We also give the proof of correctness of our algorithm in this section.
Algorithm MINISPANTREE
Input: a connected, undirected, weighted graph
G = (V, E, W) where |E| = m edges, |V| = n
vertices and W is the weight function.
Output: the set of edges that belongs to the
minimum spanning tree of G.
Begin {MINISPANTREE}
1. Initialization. Start with T = (V, fl); that is, all
the vertices and no edges.
2. Add the (n-1) least-weight edges. {We need a
sorting procedure here.}
Keep the remaining (m-n+1) edges in an active list L.
3. Do the Connected Components Procedure.
{Let k be the number of connected components and deficit = k-1.}
4. if k = 1 then terminate {We have an MST.}
otherwise
we have a collection of connected components C1, C2, ... , Ck, k>1.
5. for i = 1 to k do in parallel
From each circuit (? Ci) eliminate the
heaviest edge(s).
{a component may have zero or more than
one circuit.}
end {for}
6. Repeat
Select the lightest edge (v, w) from list L;
if v, w belong to different trees Ti and Tj then
begin
Add the edge (v, w) to either tree Ti
or Tj ;
Identify the tree so formed as Ti ;
Decrease deficit by 1
end
else
Discard the edge (v, w)
{edge (v, w) creates a cycle}
endif
Delete the edge (v, w) from the active list;
until deficit = 0
End {MINISPANTREE}
Note: In the else part of step 6 one can use the information about the discarded edge (v, w) for creating part of the cycle-history (defined later). We will exploit this information in our parallel algorithm for the MVE problem.
Definition: The non-tree edges relative to a spanning tree are called chords.
A graph G = (V,.E) with m edges and n vertices contains exactly (n-1) spanning tree edges and (m-n+1) chords. The following lemma is an elementary result in Graph Theory.
Lemma 6. The addition of a single chord (nontree edge) to a spanning tree creates exactly one fundamental cycle.
When constructing minimum spanning trees, classical MST algorithms discard certain edges on the basis that each one of these edges creates a cycle with some of the edges that have been already selected. These rejected edges will never be a part of the MST that is being constructed unless some edge updating process takes place. This arises when some of the treeedges go out of service and we need to construct an updated MST quickly. Our solution to the parallel MVE problem exploits the information on the rejected edge and those tree-edges which generated a unique cycle (see Lemma 6). What is required is some mechanism to keep track of the history of these rejected edges. The cycle-history of a rejected edge, er with respect to a minimum
spanning tree is the record (that is, a list) of all those tree edges that generated a cycle with er. The cycle-history, if available, can help us determine the entering edge f(e) corresponding to the leaving edge e quickly. For example, (see Figure 1) the cycle-history of the edge (1, 2) is {(2, 3), (1, 3)}.
The cycle-history of all the rejected edges may conveniently be stored in a table, HT in the order in which they were rejected. That is, the first entry will correspond to first rejected edge, and the second entry will correspond to the second rejected edge, and so on. It is possible that the rejected edges may appear in random order of their weights. Figure 2(g) shows the organisation of the table HT in increasing order of weights of the rejected edges.
Lemma 7. If e is a bridge of graph G then e is also a most vital edge of TG.
Proof. Observe that g(G-e) = ? and therefore g(G-e) ? g(G-e?) for every edge e? of G. Hence
6
3
2
1 15
20
10
25
Figure 1: An example of a cycle-history
cycle_history[(1, 2)] = {(2, 3), (1, 3)}
(a) A tree
6
3
2
1 15
20
10
(a part of the MST of Figure 2)
(b) Cycle formed by edge (1, 2)
the result follows. q
Note: Tarjan [9] has reported a linear order algorithm for finding the bridges of a given graph. If the graph contains a bridge(s), we may use Lemma 7 and Tarjan?s algorithm to find a most vital edge(s). Henceforth, we assume that the graphs under consideration do not have bridges.
3.1 Algorithm Parallel-MVE
Input: a connected, undirected, weighted graph
G = (V, E, W) where |E| = m edges, |V| = n
vertices and W is the weight function.
Output: the most vital edge with respect to the
minimum spanning tree of G.
Begin {Parallel-MVE}
1. Find the minimum spanning tree TG of G;
During the construction of TG record all
cycle-histories associated with the rejected
edges in the table HT in non-decreasing order
of their weights.
2. for each edge e ?TG do in parallel
{This step finds a list consisting of (n-1) pairs
of e and f(e).}
if w(e) ? the heaviest rejected edge in HT
then begin
Search in the cycle_history of the
table HT for the first occurrence of
the edge e;
f(e) := corresponding rejected edge er;
end
else begin
deficit := 1;
{only one edge to be added}
repeat
Select the lightest unconsidered
edge (v, w) from the active list;
if v, w belong to different trees T1
and T2
{It should be noted that there are
only two fragments once e is deleted
from TG.}
then begin
Add the edge f(e) := (v, w) to
either tree T1 or T2 ;
Decrease deficit by 1
end
else Discard the edge (v, w)
endif;
Mark (v, w) considered;
until deficit = 0
end
endif;
{Record the leaving edge e and the entering
edge f(e) in a list.}
end for;
3. Find the max{w(f(e)) - w(e)} for all treeedges
e in TG;
4. return the edge, e* that corresponds to the
above maximum.
end {Parallel-MVE}
Note: An illustration of the working of the parallel MVE algorithm is given in Figures 2 and 3 at the end of the paper.
Theorem 1. The edge e* computed by the Parallel-MVE algorithm is the most vital edge with respect to TG.
Proof: From Lemma 3, we know that the MVE of the given graph is one of the edges in TG. Step 1 finds the MST of G. That is, the set of (n-1) edges in TG.
Recall that the cycle-history table HT is organized into increasing order (according to weight) of the rejected edges; and also the active list L contains the unconsidered edges in increasing order of weights. The (parallel) step 2 finds the entering edge f(e) corresponding to the leaving edge e in a greedy fashion either from HT or L. The entering edge f(e) belongs to the updated minimum spanning tree TG-e (see Lemma 4).
Finally, steps 3 and 4 find the leaving edge e* that gives the maximum weight difference. By definition, e* is the most vital edge w.r.t. the TG.
This concludes the proof of the theorem. q
4. Analysis and the complexity
For a problem of size k let t(k) and p(k) denote the run time and the number of processors used respectively where k is a function of m and n. Table I lists the values of these functions for the four steps of the algorithm presented in Section 3. Step 1, the computation of the MST, uses the procedure given in Suraweera and Bhattacharya [8] and has run time O(log m) and O(m+n) processors. Organising the table HT in non-
decreasing order of weights of the rejected edges will have the same complexity. Step 2 uses (mn+1) processors and O(log n) run time. In the worst-case the table HT may have (m-n+1) rejected edges. A cycle-history of a rejected edge may contain O(n) edges in the worst-case. Therefore, one may employ the binary search procedure in parallel for each (m-n+1) rejected edge entry in HT to search the occurrences of the leaving edge in the cycle-history. The first occurrence of the leaving edge in HT can then be selected easily. Selecting the edge (v, w) from the active list L can also be done in O(log n) time on (m+n)/log n processors using a procedure due to Cole and Vishkin [3]. In the table, the two p(k) entries for step 2 are due to the if-then-else branches. Note that (m-n+1) and (m+n)/log n are both less than (m+n). Step 3, finding the maximum, requires n/log n processors and O(log.n) run time (see Valiant [11]). The last step is trivial and requires constant time.
Therefore, the total run time is O(log m) using O(m+n) processors. Since m > n, O(m+n) may further be reduced to O(m). Hence the cost (= t(k)*p(k)) of the above algorithm is O(mlog.m). It should be noted that for the above to be possible we should use the concurrent read, concurrent write (CRCW) shared memory (SM) SIMD computational model. The class of SM- SIMD computers is also known in the literature as the PRAM.
5. Conclusions
In this paper we have presented a parallel graph algorithm for the MVE problem. Our solution to the MVE problem is based on a MST algorithm and the cycle-histories of the rejected edges. The main algorithm has a run time of O(log m) on
Table I: Analysis of the steps of algorithm
Step t(k) p(k)
1
2
3
4
O(log m)
O(log n)
O(log n)
O(1)
O(m+n)
O(m-n+1)
n/log n
O(1)
or (m+n)/log n
O(m+n) processors. Since m>n, O(m+n) reduces to O(m). As such our algorithm is as good as the algorithms given in [6]. Currently we are investigating mixed-mode (heterogeneous) algorithms for the MVE problem. The flexibility of hybrid-models (SIMD/MIMD) makes them attractive candidates for further research.
References
[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.
[2] A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, Mass., 1983.
[3] R. Cole and U. Vishkin, Approximate and exact parallel scheduling with applications to list, tree and graph problems, Proc. 27th Annual Symposium on Foundations of Computer Science, 1986, pp. 478-491.
[4] R.L. Graham and P. Hell, On the history of the minimum spanning tree problem, Annals of the History of Computing 7, (January 1985), 43-57.
[5] L.-H. Hsu, R.-H. Jan, Y.-C. Lee, C.-N. Hung and M.-S. Chern, Finding the most vital edge with respect to minimum spanning tree in weighted graphs, Information Processing Letters 39, (1991), 271-281.
[6] L.-H. Hsu, P.-F. Wang and C.-T. Wu, Parallel algorithms for finding the most vital edge with respect to minimum spanning tree, Parallel Computing 18, (1992), 1143-1155.
[7] K.-C. Lin and M.-S. Chern, The most vital edges in the minimum spanning tree problem, Information Processing Letters 45, (1993), 25- 31.
[8] F. Suraweera and P. Bhattacharya, An O(log m) parallel algorithm for the minimum spanning tree problem, Information Processing Letters 45, (1993), 159-163.
[9] R.E. Tarjan, A note on finding the bridges of a graph, Information Processing Letters 2, (1974), 160-161.
[10] R.E. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, PA., 1983.
[11] L.G. Valiant, Parallelism in comparison problems, SIAM J. Computing 4, 3 (1975), 348- 355.
6
42
1 3 5
50
20
60
35
55
40
25
30
10
45
15
Figure 2: Construction of the Minimum Spanning Tree
6
42
1 3 5
6
42
1 3 5
20
25
30
10
15
10 15 20 25 30 35 40 45 50 55 60
Active List
(c) The sorted edge-weights and the Active List L for the example
Rejected
Edge cycle_history
(1, 2) (2, 3) , (1, 3)
(1, 6) (1, 3), (3, 6)
(g) History table HT
(d) the graph with the 5 least-weight edges
(a) A weighted graph with 6 vertices
and 11 edges
(b) The graph with 6 vertices and 0 edges
6
42
1 3 5
50
20
35
10
15
6
42
1 3 5
20
10
15
(e) Edges (1, 2) and (1, 6) deleted (rejected) from the corresponding cycles
(f) Edges (2, 4) and (5, 6) added from the active list giving the MST
(3, 4)
(4, 6)
(2, 3), (2, 4)
(2, 3), (3, 6), (2, 4)
Note: Active list L is left with
unconsidered edges (4, 5) and (3, 5).
(2, 3) (3, 6)( 1, 3) (1, 2) (1, 6) (2, 4) (3, 4) (4, 6) (5, 6) (4, 5) (3, 5)
6
42
1 3 5
50
20
35
10
15
6
42
1 3 5
50
20
35
10
15
6
42
1 3 5
50
20
35
15
25
(a) MST for the given graph in Figure 2 (b) Edge e = (2, 3) leaves
(c) Edge f(e) = (1, 2) enters according to Step 2
e f(e)
(2, 3)
(1, 3)
(3, 6)
(2, 4)
(5, 6)
(1, 2)
(1, 2)
(1, 6)
(3, 4)
(4, 5)
(d) Result of Step 2: a list of
the pairs e and f(e)
w(e) w(f(e))
10
15
20
35
50
(e) Result of Step 3: edge (2, 3)
the Most Vital Edge
25
25
30
40
55
w(f(e))-w(e)
15*
10
10
5
5
Figure 3: Illustration of the MVE computation
leaving edge entering edge