Algorithmica (2001) 30: 12–33 DOI: 10.1007/s004530010076

Algorithmica ©

2001 Springer-Verlag New York Inc.

Optimal Edge Ranking of Trees in Linear Time1 T. W. Lam2 and F. L. Yue3 Abstract. Given a tree, finding an optimal node ranking and finding an optimal edge ranking are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear. Key Words. Graph algorithms, Optimal node ranking, Optimal edge ranking, Time complexity.

1. Introduction. Let G be an undirected graph. A node ranking of G is a labeling of its nodes with positive integers such that every path between two nodes with the same label i contains an intermediate node with label j > i. A node ranking is optimal if it uses the least number of distinct labels among all possible node rankings. An edge ranking of G is a labeling of its edges satisfying an analogous condition, i.e., every path between two edges with the same label i contains an intermediate edge with label j > i. Figure 1 illustrates an optimal edge ranking. The node ranking and the edge ranking problems have been studied by a number of researchers as they find applications in different context [1], [6], [9], [11], [15]. Both problems are now known to be NP-hard for general graphs [13], [12], [8]. Nonetheless, in most applications, the graphs concerned are restricted to trees only. This initiates the study of node ranking and edge ranking of trees. With respect to trees, the node ranking problem seems easier than the edge ranking problem. A linear time algorithm for finding an optimal node ranking was known about a decade ago [14]. For edge ranking, the pioneering work of Iyer et al. [6] gave an approximation algorithm for finding an edge ranking with size at most twice the optimal. de la Torre et al. [3] were the first to devise a polynomial time algorithm for finding an optimal edge ranking. Their algorithm takes O(n 3 log n) time. In view of the result of the node ranking problem, it was conceivable that the time complexity could be improved. There were several other papers in the literature on developing faster algorithms for the edge ranking problem, though erroneous they are [4], [17], and [18], culminating in the O(n 2 log 1) time algorithm of Zhou et al. [16], where 1 is the maximum degree of 1

A preliminary version of this paper appeared in Proceedings of the 9th Annual ACM–SIAM Symposium on Discrete Algorithms, 1998, pp. 436–445. 2 Department of Computer Science, University of Hong Kong, Pokfulam Road, Hong Kong. [email protected]. This research was supported in part by the University of Hong Kong CRCG Grant 337/065/0026. 3 Management Information Office, City University of Hong Kong, Kowloon, Hong Kong. yolanda.yue@ cityu.edu.hk. Received April 22, 1998; revised November 19, 1998. Communicated by M.-Y. Kao. Online publication January 16, 2001.

Optimal Edge Ranking of Trees in Linear Time

13

Fig. 1. An optimal edge ranking of a tree.

the tree. In this paper we present an O(n)-time algorithm for finding an optimal edge ranking of a tree, matching the optimal result of the node counterpart. An optimal edge ranking of a tree may not be unique. In fact, the optimal edge ranking computed by our algorithm may not be the same as those by previous algorithms [3], [16]. From a conceptual viewpoint, the improvement achieved by our algorithm is rooted at a broader class of optimal edge rankings. Such a class leads to a more ambitious approach for labeling the edges—the new approach can label a group of edges at a time without optimizing for individual edges. Previous algorithms are actually based on a “guessand-test” approach, where determining a right label for an edge usually requires many guesses, each followed by a time-consuming testing. Our approach reduces the number of guesses per edge to no more than two on average and does not need to perform an explicit testing to ensure the optimality of the ranking. To make our new approach fully effective, we need some novel data structure techniques. As a warm-up, we first give an O(n log n)-time algorithm, which is based on a compact representation of labels, supplemented by a conservative merging process that avoids redundant processing of most of the labels (the latter technique is triggered by the work of Sch¨affer in the context of node ranking [14]). Then we further enhance the algorithm to run in O(n) time. The improvement stems from a tight analysis of the usage of labels. The remainder of this paper is organized as follows. Section 2 gives the basic definitions. Section 3 sketches a new approach for finding an optimal edge ranking of a tree. Section 4 gives a characterization of the ranking computed and proves that it is indeed optimal. Section 5 goes into the details about executing the new approach in O(n log n) time. The last section shows how to improve the time complexity to O(n).

2. Concepts and Notation. Following previous work [3], [16], we consider the input tree to be rooted at an arbitrary node. Note that rooting a tree does not change the definition of edge ranking, but it suggests a natural way to decompose the computation. Let ϕ be an edge ranking of a tree T with root r . An edge e of T is said to be visible if all the labels on the path from e to r are smaller than or equal to the label of e. For example, all edges incident to r are visible. It follows from the definition of ranking that all visible edges must have distinct labels. A label ` is said to be visible if there is

14

T. W. Lam and F. L. Yue

Fig. 2. A tree with an edge ranking. The set of visible labels is {5,4,3,1}.

a visible edge labeled with `. Denote by L(ϕ) the set of visible labels of T under ϕ. Figure 2 shows an edge ranking ϕ of a tree T , where L(ϕ) = {5, 4, 3, 1}. We determine the lexicographical order of two sets of labels by examining the labels in decreasing order. For instance, {5, 3, 1} < {5, 3, 2} and {3} < {5, 3, 1}. An edge ranking ϕ of T is said to be critical if L(ϕ) ≤ L(ϕ 0 ) for any edge ranking ϕ 0 of T . A critical edge ranking is an optimal edge ranking, but the converse may not be true. All critical edge rankings of T have the same set of visible labels. This set is called the critical set of T and denoted L(T ). The algorithm presented in this paper finds a critical edge ranking. The work by de la Torre et al. [3] has an important implication regarding the computation of critical edge rankings. Suppose the root of T has d children, numbered from 1 to d. We use Ti to denote the subtree of T rooted at the ith child. The edge between the root and the ith child is referred to as branch i. LEMMA 2.1 (see [3]). A critical edge ranking of T can be formed by any critical edge rankings of T1 , T2 , . . . , Td together with a suitable labeling of the branches. Lemma 2.1 suggests a bottom-up approach to compute a critical edge ranking of T : (1) Find a critical edge ranking for every subtree Ti . (2) Compute a label bi for every branch i so that this labeling together with the critical edge rankings found in (1) form a critical edge ranking of T . 2.1. Valid Labelings and Optimal Labelings. Suppose the critical edge rankings of the subtrees T1 , T2 , . . . , Td , as well as their critical sets L 1 , L 2 , . . . , L d , have been computed. We focus on labeling the branches of T . Let B = (b1 , b2 , . . . , bd ) be an arbitrary labeling of the branches of T . Define Lbi to be the set {` ∈ L i | ` > bi }. Intuitively, Lbi includes the labels of L that are still visible. B is said to be a valid labeling if, for all branches i, (i) bi 6∈ L i , and (ii) ( Lbi ∪ {bi }) ∩ ( Lbj ∪ {b j }) = φ for all branches j 6= i. It is easy to verify that a valid labeling forms an edge ranking of T . Figure 3 gives an example. A valid labeling that forms a critical edge ranking of T is called an optimal labeling. We devote Sections 3–6 to showing how to find an optimal labeling. This optimal labeling may not be the same labeling as found by previous algorithms [3], [16]; nevertheless, they all use the same set of labels.

Optimal Edge Ranking of Trees in Linear Time

15

Fig. 3. (a) L 1 = {8, 4, 3}, L 2 = {10, 9, 4}, and L 3 = {7, 1}. (b) B = (5, 6, 2) is a valid labeling. The shaded b1 = {8}, Lb2 = {10, 9}, and Lb3 = {7}. labels are no longer visible; L

2.2. Partial Labelings and Conflicts. To compute a labeling of the branches of T , our algorithm initially labels every branch of T with zero. It then increases the labels stage by stage until they form a valid labeling. We require that at the end of every stage those branches that have already received positive labels satisfy a condition similar to that of a valid labeling. Let B = (b1 , b2 , . . . , bd ) be a labeling of the branches of T , in which some bi ’s may be zero. B is said to be a partial labeling if for all branches i with bi > 0, (i) bi 6∈ L i , and (ii) ( Lbi ∪ {bi }) ∩ ( Lbj ∪ {b j }) = φ for all branches j 6= i. A partial labeling in which all branches are assigned positive labels is a valid labeling. With respect to a partial labeling B, we say that there is a conflict at a label ` > 0 if there exist two visible edges labeled with `. The definition of partial labeling guarantees that a conflict, if present, must be due to two (or more) visible edges each residing in a distinct subtree Ti such that bi = 0. For a valid labeling, there is no conflict at any label ` > 0. Thus, to produce a valid labeling, our algorithm attempts to resolve all conflicts in the current partial labeling. To resolve a conflict at ` where ` ∈ Lbi ∩ Lbj for some i 6= j, we can increase the label on one of the branches i and j to some value greater than `. The new label assigned to the branch i (or j) should be distinct from all the currently visible labels of T ; otherwise, another conflict is generated. That means, we should assign a branch with a free label, which is a positive integer not equal to any of the currently visible labels.

3. Algorithmic Framework. In this section we describe the framework of a new algorithm for finding a valid labeling of the branches of T . The discussion focuses on algorithmic aspects only, leaving out the correctness argument and implementation details. Assume that the critical sets L 1 , L 2 , . . . , L d have been computed. The algorithm starts with a partial labeling in which every label is zero. The computation is divided into a number of iterations. Each iteration increases the labels of one or more branches, producing another partial labeling. When all branches have been assigned positive labels, the partial labeling obtained is a valid labeling and the algorithm stops.

16

T. W. Lam and F. L. Yue

In each iteration, we first work out the maximum label α at which the current partial labeling B = (b1 , b2 , . . . , bd ) gives rise to a conflict. Recall that Lbi denotes the set {` ∈ L i | ` > bi }. Let K = {i | α ∈ Lbi } and let k = |K |. Our goal is to identify k − 1 free labels greater than α and assign them to any k − 1 branches in K , thus resolving the conflict at α. To attain an optimal labeling eventually, the conflict must be resolved optimally, that is, the labels to be put on the branches and the visible labels left in all subtrees are minimized lexicographically. When we choose free labels to resolve the conflict, a natural attempt is to pick the smallest k − 1 free labels starting from α + 1, say, x 1 , x2 , . . . , xk−1 . Assigning these labels to some k − 1 branches in K can resolve the conflict immediately. Yet, in some cases, this does not resolve the conflict optimally, and it is actually better to assign some xi to branches outside K . In Section 3.1 we state a condition under which assigning the free labels x1 , x2 , . . . , xk−1 to the branches in K is always the best move. We show how to handle other cases in Sections 3.2 and 3.3. 3.1. Resolving the Maximum Conflict Immediately. Consider the interval [α +1, xk−1 ]. Suppose the labels in c L 1, c L 2, . . . , c L d do not fall into [α + 1, xk−1 ]. In this case, for any b i 6∈ K , the labels in L i are either bigger than xk−1 or smaller than α. Assigning a label in {x1 , . . . , xk−1 } to a branch i 6∈ K can only eliminate labels smaller than α from Lbi . Thus, it is more beneficial to assign such a label to a branch i in K as α is eliminated from Lbi . More interestingly, a simple strategy suffices to choose which k − 1 branches in K receive the free labels x1 , . . . , xk−1 : Simple Strategy: Define Lbi |α = {` ∈ Lbi | ` ≤ α}. Let i 0 be a branch in K such ci0 |α is lexicographically smallest among all branches in K . The free labels that L x1 , x2 , . . . , xk−1 are put, in any order, on the branches in K /{i 0 }. An example is depicted in Figure 4. Notice that permuting the free labels among the k − 1 branches chosen has no effect on the visible labels left in the corresponding subtrees; thus, the strategy does not consider these k − 1 branches one by one. Assuming all previous conflicts have been resolved optimally, we can prove that the above strategy minimizes lexicographically both the labels put on the branches and the visible labels left in the subtrees (see Section 4).

Fig. 4. In this example, there are five branches. b1 = b2 = b3 = b5 = 0 and b4 = 13. The content of each b Li is represented by a number of ♣’s on the same row. There is a conflict at α = 11; K = {1, 2, 3}. The smallest two free labels bigger than α are 12 and 14. Assigning 12 and 14 to branches 1 and 3 (in any order) resolves the conflict, while minimizing lexicographically the visible labels left.

Optimal Edge Ranking of Trees in Linear Time

17

Fig. 5. (a) A rooted tree T where L 1 = L 2 = L 3 = L 4 = {5} and L 5 = {7, 8}. A conflict occurs at α = 5; K = {1, 2, 3, 4}. The smallest k − 1 free labels bigger than α are {6, 9, 10}. (b) Applying the simple strategy to resolve the conflict would label branches 2, 3, 4 with 6, 9, 10, respectively. Such an assignment cannot form a critical edge ranking. (c) A better way to resolve the conflict is first to label branch 5 with 9.

3.2. Freeing Better Labels. Should there be a visible label in some Lbi lying in the interval [α + 1, xk−1 ], applying the simple strategy directly may not resolve the conflict optimally. Figure 5 shows an example. Intuitively, if there is a visible label ` in some Lbi falling in the range [α + 1, xk−1 ], it is more advantageous to assign the free label just greater than ` to branch i instead of a branch in K because this assignment eliminates a visible label greater than α. This motivates us to handle such a case as follows: Let x j be the smallest free label among x1 , x2 , . . . , xk−1 such that there exists a branch i with Lbi containing a label lying in the interval [α + 1, x j ]. We increase the label of branch i to x j . If there are more than one such branches, we only label the branch i such that Lbi contains the biggest label in [α + 1, x j ]. Note that i may or may not be a branch in K . After labeling branch i, we get at least one additional free label less than x j . Intuitively, the new set of the smallest k − 1 free labels has a smaller lexicographic value. Now we examine the conflict at α again. If it has not been resolved, we recompute the set K and the smallest |K | − 1 free labels bigger than α. If the visible labels left in the subtrees fall outside the range spanned by these |K | − 1 free labels, we can apply the simple strategy immediately; otherwise, we repeat the procedure above. EXAMPLE. With respect to the example in Figure 5(a), a conflict occurs at α = 5, and the smallest k − 1 = 3 free labels are 6, 9, and 10. Note that c L 5 contains labels 7 and 8 which are within [5 + 1, 10]. In particular, 9 is the smallest free label bigger than 7 and c L 5 become L 5 contains a label in [6, 9]. Thus, we label branch 5 with 9. Labels 7 and 8 in c invisible, and the smallest three free labels become 6, 7, and 8. The simple strategy is applicable now. 3.3. Tackling the Boundary Case. Eventually we will come to the case where there is no conflict under the current labeling but one or more branches still get a label zero. To produce a valid labeling, we must find a free label for each of these branches. In this case, we say that we are resolving a virtual conflict at 0. Let α = 0 and K = {i | bi = 0}.

18

T. W. Lam and F. L. Yue

If the currently visible labels in all subtrees fall outside the range spanned by the |K | smallest free labels, we assign the |K | smallest free labels to the branches in K in an arbitrary order. Otherwise, we execute the procedure in Section 3.2 to label a branch not necessary in K so as to generate more smaller free labels. 3.4. The Algorithm. The computation described in the previous sections is put together into a procedure called LABELING, as shown in Figure 6. The main body of the procedure LABELING is a while loop comprising Steps II–V. Each iteration attempts to resolve the currently maximum conflict. If there are enough suitable free labels available, the

Fig. 6. LABELING(T ).

Optimal Edge Ranking of Trees in Linear Time

19

conflict is resolved immediately; otherwise, more smaller free labels are generated. At the end of each iteration, the labels stored in the array B define a partial labeling. The positive labels in use always form a subset of the labels used by an optimal labeling (see Section 4). That means the procedure never uses a “wrong” label. On exiting from the while loop, B[1], B[2], . . . , B[d] are all positive and form a valid labeling. In Section 4 we give a characterization of this valid labeling and prove that it is actually optimal. Based on the procedure LABELING, we can construct an algorithm for computing a critical edge ranking of a rooted tree R. For each node v in R, let Rv denote the subtree in R rooted at v. We execute LABELING(Rv ) for each internal node v of R in a bottom-up manner. The input to LABELING(Rv ) consists of the critical sets of the subtrees rooted at the children of v. This simple algorithm is referred to as EDGE-RANKING.

4. Proof of Optimality. In this section we prove that the procedure LABELING computes an optimal labeling. The discussion divides into two parts: Section 4.1 defines a class of valid labelings, which characterizes the labeling computed by our procedure; Section 4.2 shows that all intermediate partial labelings, as well as the final valid labeling, computed by our procedure are kept to a minimum, thus leading to an optimal labeling. Let T be a rooted tree. Recall that the subtrees rooted at the children of T and their critical sets are denoted T1 , T2 , . . . , Td and L 1 , L 2 , . . . , L d , respectively. The discussion below uses a notation hBi to denote the set of nonzero labels in a partial or valid labeling B of the branches of T . 4.1. The Relaxed Greedy-Cover Labeling. It is known that all optimal labelings of the branches of T must use the same set of labels [3]. We denote 6 as this set. Two optimal labelings differ only in the order the labels of 6 are assigned to the branches. The set of labels used by any valid labeling must be lexicographically bigger than or equal to 6. Figure 7 depicts an example. Not every valid labeling using 6 is optimal. The edge ranking algorithm by de la Torre et al. [3] is based on the existence of a greedily constructed labeling which is guaranteed to be optimal. The greediness of such a labeling is captured by the following notion. Recall that L i |x denotes the set {` ∈ L i | ` ≤ x}. DEFINITION. Let B = (b1 , b2 , . . . , bd ) be a valid labeling. A branch i is said to satisfy the greedy-cover (abbreviated as gc) property if for all branches j with b j <

Fig. 7. (a) A tree of which any optimal labeling must use the labels {1, 6, 7, 8}. The labelings given in (b) and (c) are optimal while the one in (d) is not.

20

T. W. Lam and F. L. Yue

bi , L i |bi  L j |bi .4 B is said to be a gc labeling if every branch satisfies the gc property. Intuitively, a gc labeling assigns the biggest label to a branch so as to cover the lexicographically biggest set of labels. The branch indices are used to break a tie. The labeling shown in Figure 7(b) is a gc labeling. Among all labelings using 6, there is a unique gc labeling, which causes the smallest set of visible labels left in the subtrees, and which is thus optimal. The optimal labeling computed by our algorithm does not follow the rule imposed by a gc labeling. We observe that with respect to a gc labeling Z = (z 1 , z 2 , . . . z d ), if there are branches i, j such that both L i and L j contain no labels between z i and z j inclusive, then z i and z j can be swapped without affecting the optimality of the labeling. See Figure 7(b) and (c) for an example. Below, we relax the definition of a gc labeling to capture the above observation. DEFINITION. Consider any valid labeling B = (b1 , b2 , . . . , bd ). A branch i is said to satisfy the relaxed greedy-cover (abbreviated as rgc) property if for all branches j with b j < bi , L i |bi  L j |bi or both L i and L j contain no labels in the interval [b j , bi ]. B is called an rgc labeling if every branch satisfies the rgc property. A gc labeling is also an rgc labeling, but the converse is not true. Also, unlike a gc labeling, an rgc labeling using 6 may not be unique. Consider any rgc labeling B using 6. By definition, the labels of B can be permuted to produce a gc labeling B¯ that is ¯ and B¯ causes the same set of visible labels equivalent to B in the sense that hBi = h Bi left in every subtree Ti as B. Therefore, if B is equivalent to the gc labeling using 6, B must be optimal. DEFINITION.

Consider any partial labeling P = (b1 , b2 , . . . , bd ).

(i) P is a gc-partial labeling if for any branch i such that bi > 0, for any branch j such that b j < bi , L i |bi  L j |bi . (ii) P is an rgc-partial labeling if for any branch i such that bi > 0, branch i satisfies the rgc property. Given an rgc-partial labeling P, one can always permute the labels on the branches to produce a unique gc-partial labeling P¯ equivalent to P. We call P¯ the gc equivalent of P. 4.2. Invariant.

The way we construct the procedure LABELING enforces that

• the partial labeling P produced at the end of each iteration of the While loop is an rgc-partial labeling, and • every positive label used by P is bigger than α(P), where α(P) denotes the maximum label at which there is a conflict. We are still using the lexicographical order, but a tie is broken using the branch indices. That is, L i |x  L j |x if and only if L i |x is lexicographically greater than L j |x or the two sets are equal and i > j. 4

Optimal Edge Ranking of Trees in Linear Time

21

In this section we prove a more important invariant, namely, • hPi ≤ 6. These invariants together imply that when LABELING terminates, it produces a valid labeling B with hBi ≤ 6. Every valid labeling uses a set of labels lexicographically no smaller than 6. Thus, we conclude that hBi = 6 and B is an optimal labeling. The above invariants seem a bit simple, yet we can derive from them two stronger properties concerning the quality of P, which will be used in our induction proof of the invariant hPi ≤ 6. The first property states that hPi is actually a subset of 6; the second one gives a piecewise relationship between the gc equivalent of P and the gc labeling Z using 6. Figure 8 gives an illustration. LEMMA 4.1. Suppose P is an rgc-partial labeling such that every positive label used by P is bigger than α(P) and hPi ≤ 6. Then the following properties hold. Property 1. hPi ⊆ 6. Property 2. Let P¯ = (c1 , c2 , . . . , cd ) be the gc equivalent of P. Let Z = (z 1 , z 2 , . . . , z d ) be the gc labeling using 6. Then ci ≤ z i for every branch i. ¯ = {ci1 , ci2 , . . . , cit }, PROOF. We prove the lemma by backward induction. Let h Pi where 0 < ci1 < ci2 < · · · < cit . Below, we prove that, for any j from t down to 1, if ci j+1 , . . . , cit ∈ 6, and ci j+1 ≤ z i j+1 , . . . , and cit ≤ z it , then ci j ∈ 6 and ci j ≤ z i j . To ease our discussion, we use δ to denote ci j . ¯ = hPi ≤ 6 Suppose, by way of contradiction, that δ 6∈ 6. Due to the fact that h Pi and the induction hypothesis that ci ∈ 6 and ci ≤ z i for all i ∈ {i j+1 , . . . , i t }, there must exist a branch h ∈ {i 1 , . . . , i j } such that z h > δ. Suppose we modify Z by decreasing the label of branch h to δ. Let Z 0 be the resultant labeling. Because Z is already an optimal labeling, Z 0 cannot be a valid labeling and must contain at least one conflict, say, at a label x. If x = δ, then δ must exist in a critical set L w for some branches w ∈ {i 1 , i 2 , . . . , i j }. This contradicts that P, involving δ, is a partial labeling. It remains to consider x > δ. That is, x originates from L h , as well as some L l where l ∈ {i 1 , . . . , i j } − {h}. With respect to P¯ and P, this conflict remains. This contradicts the invariant that every label in hPi (including δ) is bigger than α(P). Therefore, we conclude that δ ∈ 6. Suppose, by way of contradiction, that δ > z i j . Since δ ∈ Z , there is a branch l ∈ {i 1 , . . . , i j−1 } such that zl = δ. That is, zl > z i j . We derive a contradiction as follows: (i) Z is the gc labeling, so L l |δ Â L i j |δ . (ii) Consider the label cl . Since l ∈ {i 1 , . . . , i j−1 }, we know that cl < δ. Recall that P¯ is a gc-partial labeling, we have L i j |δ Â L l |δ . A contradiction occurs. Therefore, δ ≤ z i j . The rest of this section is devoted to an inductive proof of the invariant hPi ≤ 6. Initially, the procedure LABELING assigns every branch a label zero, so the invariant holds. Suppose that after a number of iterations of the while loop, the rgc-partial labeling P produced satisfies the invariant. In the next iteration, one or more branches will receive bigger labels. Let Q be the new rgc-partial labeling. We are going to show that hPi < hQi ≤ 6.

22

T. W. Lam and F. L. Yue

Fig. 8. (a) A tree with an optimal gc labeling Z = (9, 8, 7, 6, 1). (b)–(e) The partial labeling P computed at ¯ It is easy to verify that P the end of each iteration of the while loop, and the corresponding gc equivalent P. is an rgc-partial labeling, and that all positive labels used by P are bigger than α(P) and are used by Z .

We have a close look of the iteration that produces Q at the end. Steps II and III compute the values of α, K , k, γ , and w with respect to P. New labels are assigned to the branches in one of the Steps IVa, IVb, and IVc. Lemmas 4.2, 4.4, and 4.5 consider these three steps separately, proving the invariant hQi ≤ 6 in each case. ¯ the gc equivalent of P, equal (c1 , c2 , . . . , cd ). Let P = (b1 , b2 , . . . , bd ). Let P, LEMMA 4.2 (for Step IVc). Suppose α = 0 and k ≤ w. Let W be the set of the k smallest free labels. Let Q be the labeling formed by assigning the labels in W to the k branches in K . Then hQi ≤ 6.

Optimal Edge Ranking of Trees in Linear Time

23

PROOF. With respect to P, the label of every branch i in K is zero. Thus, Q has exactly ¯ ∪ W . We k positive labels more than P and hQi = hPi ∪ W . hQi = hPi ∪ W = h Pi ¯ want to show that 6 ≥ h Pi ∪ W , then the lemma follows. Let Z = (z 1 , z 2 , . . . , z d ) be the gc labeling using 6. Let 61 = {z i | ci > 0}. Property 2 of P states that z i ≥ ci ¯ Let 62 be the (d − |61 |) smallest for every branch i. Thus, 61 ≥ {ci | ci > 0} = h Pi. positive integers distinct from 61 . Obviously, 6 ≥ 61 ∪ 62 . Although it may not be ¯ true that 62 ≥ W , we can conclude, from the definition of W and the fact 61 ≥ h Pi, ¯ that 61 ∪ 62 ≥ h Pi ∪ W . LEMMA 4.3.

Suppose α > 0. For any branch i ∈ K , ci = bi = 0.

PROOF. Recall that with respect to a partial labeling, a conflict arises from branches with label zero. Thus, bi = 0 for all i ∈ K . Suppose to the contrary that there exists i ∈ K such that ci > 0. Since every positive label in P is greater than α, ci must be greater than α, too. Note that α is a positive label in L i , and ci causes the label α in L i to become invisible, though bi = 0 does not. This contradicts the second property of a gc equivalent. Therefore, ci = 0 for all i ∈ K . LEMMA 4.4 (for Step IVb). Suppose α > 0 and k −1 ≤ w. Let W be the set of the k −1 smallest free labels bigger than α. Let Q be the partial labeling formed by assigning the labels in W to any k − 1 branches in K . Then hQi ≤ 6. ¯ ∪ W . We are going to show that 6 ≥ h Pi ¯ ∪ W. PROOF. Again, hQi = hPi ∪ W = h Pi Let Z = (z 1 , z 2 , . . . , z d ) be the gc labeling using 6. Let 61 = {z i | i 6∈ K }. Since z i ≥ ci for every branch i, we have 61 ≥ {ci | i 6∈ K }. Lemma 4.3 implies that ¯ In short, 61 ≥ h Pi. ¯ Let 62 be the set of k − 1 smallest labels that {ci | i 6∈ K } ≥ h Pi. are bigger than α and distinct from 61 . Note that Z must assign at least k − 1 branches in K with label > α (otherwise, Z is not a valid labeling). Therefore, 6 = hZ i ≥ 61 ∪ 62 ¯ ∪ W. ≥ h Pi LEMMA 4.5 (for Step IVa). Suppose α = 0 and k > w or α > 0 and k − 1 > w. Let x be the smallest free label bigger than γ . Let j be the branch such that b L[ j] contains the biggest label smaller than x. Let Q be the partial labeling formed by relabeling the branch j to the value x in P. Then hQi ≤ 6. ¯ − {b j }) ∪ {x}. Due to Property 1 of P, we have 6 ⊇ h Pi. ¯ Below PROOF. hQi = (h Pi ¯ Then 6 ≥ h Pi ¯ ∪ {x} we show that 6 contains at least one label ` ≥ x such that ` 6∈ h Pi. ≥ hQi. To prove the existence of such an `, we prove the following two statements. Let p = |hPi| (i.e., the number of positive labels used by P). Recall that w denotes the number of free labels in the interval [α + 1, γ − 1] with respect to P. I. 6 contains more than p + w labels bigger than α. ¯ contain the same set of labels ≥ x, then 6 contains at most p + w II. If 6 and h Pi labels bigger than α.

24

T. W. Lam and F. L. Yue

¯ Statements I and II together imply that 6 must contain a label ` ≥ x such that ` 6∈ h Pi. ¯ Thus, 6 ≥ h Pi ∪ {x} ≥ hQi, and Lemma 4.5 follows. Proof of Statement I. If α = 0 and k > w, every label in 6 is greater than α = 0, and |6| = d = p + k > p + w. It remains to consider the case where α > 0 and k − 1 > w. Let Z = (z 1 , . . . , z d ) be the gc labeling using 6. For each i such that ci > 0, i is not in K (due to Lemma 4.3), and z i ≥ ci > α. On the other hand, Z must assign at least k − 1 branches in K with label bigger than α. Thus, Z uses at least p + k − 1 > p + w labels greater than α. Proof of Statement II. Suppose P¯ and 6 have the same set of labels ≥ x. Let Z = (z 1 , . . . , z d ) be the gc labeling using 6. Since both P¯ and Z are gc labelings, for each ¯ such that h ≥ x, h lies on the same branch under both P¯ and Z . This can label h ∈ h Pi be proved using an induction starting with the largest label. Furthermore, P¯ and Z must have the same set of labels in the range [γ , x − 1]. More precisely, for any label h ∈ [γ , x − 1], if h is used by P¯ then h is also used by Z and h labels the same branch with respect to both P¯ and Z ; otherwise, h is the label of a visible edge residing in the same subtree Ti with respect to both P¯ and Z . This can be proved by a backward induction starting with h = x − 1. ¯ In summary, P¯ and Z use the same set of labels ≥ γ . With respect to P (or P), let p1 be the number of labels ≥ γ , and let p2 be the number of labels in the interval [α + 1, γ − 1]. Note that p = p1 + p2 . Z uses exactly p1 labels ≥ γ . Recall that w.r.t. P, w denotes the number of free labels in the interval [α + 1, γ − 1], and no visible labels residing in any subtrees fall into this interval. Thus, p2 + w = γ − 1 − α. The number of labels in hZ i that are bigger than α is at most p1 +(γ −1−α) = p1 + p2 +w = p +w. In conclusion, based on Lemmas 4.2–4.5, we can show inductively that the partial labeling P computed in every iteration of the while loop satisfies the invariant hPi ≤ 6.

5. O(n log n)-Time Algorithm. Recall that, given a tree R, the algorithm EDGEinvokes the procedure LABELING for every subtree Rv rooted at an internal node v of R. A brute-force implementation of LABELING would enable EDGE-RANKING to run in O(n 2 ) time, where n is the number of nodes in R. In this section we give a more efficient implementation of LABELING, improving the time complexity of EDGERANKING to O(n log n). This implementation is based on two novel ideas, namely, a compact representation of the critical set and a conservative merging process that avoids redundant processing of most of the labels. RANKING

5.1. Segments. For any integers ` ≤ r , denote by [`, r ] the segment of consecutive integers from ` to r . Any set L of labels can be expressed as a union of segments [`1 , r1 ], [`2 , r2 ], . . . , [`s , rs ] where ri < `i+1 − 1 for i = 1, 2, . . . , s − 1. The number of segments of L may be as many as the number of distinct labels in L. Yet, if L is the √ critical set of a tree R with n nodes, there are at most n disjoint segments. L(R) = LEMMA 5.1. Suppose √ `s < n and s < n.

Ss

i=1 [`i , ri ]

where ri < `i+1 − 1. Then `1 + `2 + · · · +

Optimal Edge Ranking of Trees in Linear Time

25

Ss PROOF. We prove that if L(R) = i=1 [`i , ri ] where ri < `i+1 − 1, then R contains , ` , . . . , `s edges. Thus, `1 + `2 + · · · + `s <√n. s disjoint subtrees having at least ` 1 2 Ps `i ≥ 1 + 3 + · · · + (2s − 1) = s 2 . It follows that s < n. Because ri < li+1 − 1, i=1 Let ψ be a critical edge ranking of R suchSthat the restriction of ψ to every subtree of s [`i , ri ]. Consider the visible edge that R is also critical. That is, L(ψ) = L(T ) = i=1 is assigned with the label `s under ψ. Denote this edge by es = (u, v) where u is the parent of v in R. We first prove that the subtree Rv contains at least `s − 1 edges. If `s = 1, it is trivial that Rv contains at least `s − 1 edges. Below, we assume that `s > 1. The label (`s − 1) is not visible in R. We consider the following two cases: • (`s − 1) is visible in Rv . The restriction of ψ to Rv is critical. Since a critical edge ranking of Rv does not use a label greater than the number of edges in Rv , there must exist at least (`s − 1) edges in Rv . • (`s − 1) is not visible in Rv . The following argument shows that this case cannot happen. The label (`s − 1) is not visible in R, and every label on the path from u to the root of R is at most `s − 2. It follows that `s − 1 is also not visible in Ru . We relabel the edge es with (`s − 1). Then we obtain an edge ranking of R with a visible set of labels that is lexicographically smaller than L(ψ). A contradiction occurs. In short, the subtree rooted at the edge es (i.e., Rs plus the edge es ) contains at least `s edges. Next, we show that R contains another disjoint subtree with `s−1 edges. Let T 0 be the subtree of R formed by deleting all the subtrees rooted at a visible edge with ≥ `s . Slabel s−1 The labels inherited from ψ still form a critical ranking of T 0 , and L(T 0 ) = i=1 [`i , ri ]. Let es−1 be the visible edge with the label `s−1 in T 0 . Again, we can argue that the subtree rooted at the edge es−1 in T 0 contains at least `s−1 edges. Repeating the argument above, we can show that there are s disjoint subtrees in R having `s , `s−1 , . . . , `1 edges. 5.2. Data Structures. We manipulate a set of visible labels segment by segment instead of label by label. The critical set of every subtree Rv (i.e., L(Rv )) is represented as a search tree X . Every segment [`, r ] in X is associated with a flag f ∈ {0, 1}, and the search key is the ordered pair ( f, r ). A segment of labels in L(Rv ) is put into X as a flag-1 segment, while a segment of labels not in L(Rv ) forms a flag-0 segment in X . Operations to be performed on X include: insert a segment, delete a segment, and search for the existence (or predecessor and successor) of a segment. Any subtree of R contains at most n nodes and X contains at most n − 1 segments. Each of the above operations can be performed in O(log n) time. Our procedure needs to count the number of free labels between two consecutive flag-1 segments. To ease the job, we store a counter in every consecutive pair of flag-1 segments. 5.3. Implementation of LABELING(Rv ). Consider an internal node v of R. Let u 1 , u 2 , . . . , u d be the children of v. Without loss of generality, we assume that the subtree Ru 1 contains the largest number of nodes among all subtrees rooted at the children of v. The input to LABELING(Rv ) consists of d search trees, X [1], X [2], . . . , X [d], representing L(Ru 1 ), L(Ru 2 ), . . . , L(Ru d ). Regarding the output, LABELING produces an array B[1..d] representing the branch labels and a search tree X representing L(Rv ). Note that X

26

T. W. Lam and F. L. Yue

inherits those segments from X [1], X [2], . . . , X [d] that represent labels still visible from the viewpoint of Rv . To save time, we do not build X starting from scratch. Instead we use X [1] as a basis and merge segments from other input search trees into X [1]. At the end, we return X [1] as the output for Rv . Ru 1 is the biggest subtree and possibly contains a large number of segments. If we avoid copying the content of X [1], we potentially save a lot of time. Our goal is to charge the time for executing LABELING(Rv ) to the following number of tree operations: • d—the number of children of v; • s—the total number of segments in L(Ru 2 ), . . . , L(Ru d ); • h—the number of segments in L(Ru 1 ) that are no longer visible when LABELING(Rv ) terminates and labels the branches of v with B[1..d]. The main result in this section is that LABELING(Rv ) can be executed O((d + s + h) log n) time. Basically, we need an efficient implementation of the while loop (Steps II– V) inside LABELING so as to achieve the time bound. To start, we put together all flag-1 segments in X [2], . . . , X [d] into a list S that is sorted in descending order of the right limits of the segments (a tie is broken according to branch indices). In order to recover the sources of these segments in the future, segments originating from the same tree, say, X [i], are linked together in S and they each store the index i. The following implementation is based on the invariant that, at the time when the maximum conflict, say, at α, is resolved, all segments originating from L(Ru 2 ), . . . , L(Ru d ) that are greater than α and still visible from the viewpoint of Rv must have been inserted into X [1]. Also, all labels that are bigger than α and still free from the viewpoint of Rv are kept in X [1] as flag-0 segments. The following two lemmas captures the core of the implementation, showing how to locate the maximum conflict efficiently and resolve the conflict, respectively. LEMMA 5.2. Step II (locate the maximum conflict) can be implemented in O((s + h) log n) time in the course of executing LABELING(Rv ). PROOF. The segments in S are examined one by one in decreasing order. If a segment [`, r ] does not cause a conflict (precisely, [`, r ] does not overlap with the next segment in S and any flag-1 segment in X [1]), we insert [`, r ] with flag 1 into X [1]. Such a case happens at most s times and costs O(s log n) time. If [`, r ] causes a conflict, we identify all other segments in S and X [1] causing this conflict. Let α be the maximum label in [`, r ] where the conflict occurs, and let K be the set of all the branches i that give rise to this conflict. Note that if α < r , the segment [α + 1, r ] is currently visible from the viewpoint of Rv but not of Ru 1 . Before resolving the conflict at α, we need to update X [1] in order to maintain the invariant of X [1]. We split [`, r ] into two segments: [`, α] remains in S and [α + 1, r ] is inserted into X [1] with flag 1. The insertion of [α + 1, r ] is accompanied with an update to the corresponding flag-0 segment in X [1]. Time complexity: To identify α and K , Step II examines at most |K | + 1 segments from S and one segment from X [1]. After the conflict at α is resolved (in one or more iterations of Steps III–V), at least |K | − 1 of such segments become invisible and have been removed from S or X [1] in Step V. Step II is then executed again. Note that |K | ≥ 2,

Optimal Edge Ranking of Trees in Linear Time

27

and the sum of (|K | − 1) over all iterations of Step II is at most s + h. Thus, Step II over all iterations examines at most O(s + h) segments and uses O((s + h) log n) time. To resolve a conflict, Step III counts the number of suitable free labels using X [1], then Step IV finds the relevant free labels and determines the branches for label assignment. The latter process may access many flag-1 segments in S and X [1] so as to break the tie. Afterwards most of these segments become invisible and are removed from further examination at Step V. Note that the conflict may not be resolved after one iteration of Steps III–V. To save time, these three steps are repeated until the current conflict is resolved. Then the control is passed to Step II to identify the next conflict. Details are given below. LEMMA 5.3. Step III (count the suitable free labels) can be implemented in O((s + h + 1) log n) time in the course of executing LABELING(Rv ). PROOF. Step III is implemented as follows. We locate the smallest flag-1 segment [x, y] in X [1] such that y > α. If [x, y] does not exist, we set w, the number of suitable free labels, to |K |. If [x, y] exists and x > α, we let w be the number of free labels in [α + 1, x − 1], which is computed by looking up the free label counter stored between the segment [x, y] and its flag-1 predecessor in X [1]. Otherwise, w = 0. Time complexity: Each execution of Step III costs only O(log n) time. Since Step III always executes together with Step IV, it suffices to bound the number of times Step IV executes. Note that for each branch that gets labeled in Step IVa or IVb, one or more segments in its subtree have become invisible and removed from S or X [1] in Step V. Thus, Steps IVa and IVb together execute at most s + h times. Step IVc executes at most once since the while loop terminates afterwards. Thus, the total time spent on Step III is O((s + h + 1) log n). LEMMA 5.4. Step IV can be implemented in such a way that in the course of executing LABELING(Rv ), Steps IVa (free more labels) and IVb (resolve a conflict at α > 0) altogether take O((s + h) log n) time, and IVc (resolve the conflict at zero) takes O(d log n) time. PROOF. With X [1], implementing Step IVa is straightforward. Recall the segment [x, y] found in Step III. Let z be the smallest free label in X [1] bigger than y. Search X [1] to locate the largest flag-1 segment [a, b] with b < z. If [a, b] originates from the tree X [ j], set B[ j] to x. Step IVb is slightly more complicated. If α > 0, we need to determine the branch i 0 in K that minimizes the set L i0 |α lexicographically. Here, we use a brute-force method. We examine, for each i ∈ K , the flag-1 segment originating from X [i] and containing the label α; i 0 should correspond to the segment with the largest left limit. In case there is a tie, we further examine the next smaller segments until i 0 can be determined. Then we delete the |K | − 1 smallest free labels bigger than α from X and assign them to the branchs in K excluding i 0 . The running time of Steps IVa and IVb are dominated by the number of segments accessed, which can be charged to the number of segments that become invisible and

28

T. W. Lam and F. L. Yue

get removed in Step V. Thus, in the course of executing LABELING(Rv ), these two steps use at most O((s + h) log n) time. Step IVc executes only once. When α = 0, we delete the |K | smallest free labels bigger than α from X [1] and assign them to the branches in K . Unlike the previous case, the running time of Step IVc cannot be charged to the number of segments that become invisible. Nevertheless, |K | ≤ d and this step takes O(d log n) time. Step V (remove labels no longer visible) is relatively simple. For each i such that B[i] has just received a new value, we update X [1] or S to delete all flag-1 segments with labels less than B[i] and with branch index i. If i is in K , we delete i from K . If K still contains two or more indices, the conflict at α has not been resolved completely and the control goes to Step III direct. Since Step V can remove O(s + h) segments, it takes O((s + h) log n) time. When the while loop terminates, all flag-1 segments that are initially found in X [2], . . . , X [d] and that are still visible should have already been inserted in X [1]. Recall that we expect X [1] to represent L(Rv ) eventually. We need an extra step (Step VI) to insert the branch labels into X [1] and merge consecutive flag-1 segments in X [1]. This takes O((d + s) log n) time. In conclusion, LABELING(Rv ) can be executed in O((d + s + h) log n) time. THEOREM 5.1. It takes O(n log n) time to execute EDGE-RANKING(R), where n is the number of nodes in R. PROOF. To ease our discussion, we add a subscript v to thePvariables d, s, h from now on. The algorithm PEDGE-RANKING on input R runs in O( v∈R (dv + sv + h v ) log n) time. Obviously, v∈R dv is bounded by n. Regarding h v , we observe that once an edge becomes not visibleP in the subtree Rv , it will remain not visible in any subtree P rooted at an ancestor of v. Thus, v∈R h v is also bounded by n. It remains to show that v∈R sv equals O(n). Suppose the subtrees rooted at the children of a node v contain n 1 , n 2 , . . . , n dv nodes. Without loss of generality, assume n 1 = max{n 1 , n 2 , P . . . , n dv }. By Lemma 5.1, √ √ √ √ + · · · + n dv . We can prove by induction on n that sv ≤ n 2√ v∈R ( n 2 + · · · + n dv ) P ≤ 4n − 4 n. Therefore, v∈R sv = O(n). To pave the way for computing an optimal edge ranking in linear time, we need a slight improvement of the above implementation of LABELING. As stated in the following lemma, we want to replace the term d log n with d + b log n, where b is the number of segments partitioning the branch labels computed by LABELING(Rv ). LEMMA 5.5.

It takes O(d + (b + s + h) log n) time to execute LABELING(Rv ).

PROOF. The term d log n is due to Steps IVc and VI. For the former, we could assume the search tree X [1] supports in O(1) time searching the smallest flag-1 segment and removing the smallest flag-0 segment. Then Step IVc can be immediately improved to O(d) time. For Step VI, the major concern is how to group the branch labels into segments in O(d) time. Notice that sorting the labels would be too inefficient. We achieve the linear

Optimal Edge Ranking of Trees in Linear Time

29

time bound by making use of an auxiliary array.5 Therefore, inserting the segments of branch labels into X [1] takes O(d + b log n) time. 6. O(n)-Time Algorithm. Lemma 5.5 implies that the algorithm EDGE-RANKING(R) runs in time à ! X X O dv + (sv + h v + bv ) log n . v∈R

v∈R

The linear time improvement is based on an observation that most of the time EDGERANKING deals with segments containing small labels. More specifically, a segment [`, r ] is said to be small if r < log2 n; otherwise [`, r ] is said to be big. We decompose the value sv into two values, sv0 and sv00 , corresponding to the number of big and small segments, respectively. Similarly, h v can be decomposed into h 0v and h 00v and bv into bv0 and bv00 . To handle small segments more efficiently, we devise a hybrid representation that uses different data structures for small segments and big segments. This hybrid representation is able to support search, insert, and delete operations in O(1) time for small segments, and in O(log n) time for big segments (see Section 6.2). Using such a hybrid representation, we immediately improve the time complexity of LABELING(Rv ) to O(dv + sv00 + h 00v + bv00 + (sv0 + h 0v + bv0 ) log n), and EDGE-RANKING(R) to ! Ã X X 00 00 00 0 0 0 (dv + sv + h v + bv ) + (sv + h v + bv ) log n . O P

v∈R

v∈R

sv00 ,

h 00v , and bv00 are upper bounded by sv , h v , and bv , bv0 ) = O(n). In Section 6.1 we prove that there

Note that v∈R dv = Pn − 1. Also, respectively. We have v∈R (sv0 + h 0v + are not too many large segments. More precisely, ¶ µ µ ¶ X X X n n 0 . bv0 and h 0v = O s = O and v log n log2 n v∈R v∈R v∈R P Therefore, v∈R (sv0 + h 0v + bv0 ) = O(n/ log n) and we can conclude with the following theorem. THEOREM 6.1. O(n) time.

An optimal edge ranking of a tree with n nodes can be computed in

6.1. Large Segments. Assume R is labeled in accordance with the algorithm EDGERANKING. That is, R, as well as every subtree in R, receives a critical edge ranking. Consider an internal node v in R and the labels of the branches of v. These labels themselves are partitioned into a number of segments. Let [l, r ] be one such segment. Let (v, u) and (v, w) be the branches labeled with l and r , respectively. If r ≥ log2 n, we call r a leader. Note that no branches of v are labeled with (r + 1) or (l − 1). 5 Let A[1..n] be an array initialized to some special value. Note that the initialization can be done in O(1) time (see e.g., [10]). For 1 ≤ i ≤ d, let A[B[i]] = i. Then, using A, we can easily detect whether each B[i] marks the beginning or the end of a segment.

30

LEMMA 6.1.

T. W. Lam and F. L. Yue

Ru contains at least l − 1 edges.

PROOF. Suppose to the contrary that Ru contains less than l − 1 edges. Then no edges in Ru are labeled with l − 1. Contradiction is derived as follows: • (l − 1) is not visible in Rv . Decrease the label of (v, u) to (l − 1). This produces a “better” ranking of Rv , contradicting the fact that the original ranking of Rv is critical. • (l − 1) is visible in Rv . Assume (l − 1) is visible in Rz for some child z 6= u of v. The label of (v, z), denoted by x, is less than l − 1. Relabel (v, u) with l − 1 and (v, z) with l. Then the set of visible labels in Rv gets smaller; in particular, x is eliminated. This contradicts the fact that the original ranking of Rv is critical. LEMMA 6.2.

There are O(n/log2 n) edges in R such that their labels are leaders.

PROOF. Let e = (v, w) be an edge whose label r is a leader. Denote [l, r ] as the segment of branch labels of v ending at r . By definition, r ≥ log2 n; so the number of edges in Rv , denoted |Rv |, is at least log2 n. Let (v, u) be the branch of v labeled with l. Depending on the number of edges in Ru , we give different arguments to show that such edges e cannot appear too many times in R. Case 1: |Ru | < log2 n. In this case, we observe that the sum of |Ru | + |[l, r ]| over all such edges is bounded by 2(n − 1). On the other hand, by Lemma 6.1, |Ru | ≥ l − 1; thus, |Ru | + |[l, r ]| ≥ r ≥ log2 n, and Case 1 occurs at most 2(n − 1)/log2 n times. Case 2: |Ru | ≥ log2 n. Case 2(a): v has one or more children y 6= u such that |R y | ≥ log2 n. The number of occurrences of Case 2(a) is bounded by the number of nodes u in R such that |Ru | ≥ log2 n and u has a sibling y where |R y | ≤ log2 n. Such a node u, as well as Case 2(a), occurs at most 2(n − 1)/log2 n times. Case 2(b): u is the only child of v with |Ru | ≥ log2 n. Let dv be the number of children of v. Let tv be the total number of edges in the subtrees rooted at the children of v other than u. The sum of (tv + dv ) over all such nodes v is at most n − 1. Let kv be the number of edges visible in Ru but not visible in Rv . The sum of kv over all such nodes v is at most n − 1. In what follows, we argue that tv + dv + kv + |[l, r ]| > log2 n. The sum of |[l, r ]| over all such nodes v is at most (n − 1). Case 2(b) occurs at most 3(n − 1)/log2 n times. • If tv + dv ≥ l, then tv + dv + |[l, r ]| ≥ l + |[l, r ]| = r + 1 > log2 n. • Suppose tv + dv < l. We claim that all labels in the range [tv + dv , l − 1] are visible in Ru . It follows that kv ≥ |[tv + dv , l − 1]| and tv + dv + kv + |[l, r ]| = r + 1 > log2 n. The claim is proved as follows. Suppose to the contrary that there exists some label in [dv + tv , l − 1] that is not visible in Ru and x is the largest of such labels. Relabel all branches of v, except (v, u), with the labels tv + 1, tv + 2, . . . , tv + dv − 1, and lower the label on (v, u) to x. This gives a “better” ranking of Rv , contradicting the fact that the original ranking of Rv is critical. COROLLARY 6.1.

The sum of bv0 over all internal nodes v is O(n/log2 n).

Optimal Edge Ranking of Trees in Linear Time

31

LEMMA 6.3. Consider a big segment [l, r ] in the critical set of a subtree Ru . Let (x, y) be the visible edge in Ru having the label r . Then the label of (x, y) is a leader with respect to x. PROOF. No visible edges in Ru have the label r + 1. Suppose to the contrary that the label r of (x, y) is not a leader. Then some branch of Rx , (x, z) say, gets the label r + 1. Since r is visible in Rv , all labels on the path from x to v are smaller than r . Thus, (x, z) is also visible in Ru , contradicting the fact that Ru contains no visible edges with the label r + 1. LEMMA 6.4.

The sum of h 0v over all internal nodes v is at most O(n/log2 n).

PROOF. Let v be an internal node of R and let u be the child of v with the biggest subtree. By Lemma 6.3, h 0v is bounded by the number of visible edges e in Ru such that the label of e is a leader and e is not visible in Rv . Note that once e becomes not visible in Rv , e is not visible in all subtrees rooted at an ancestor of v in R. That means, every edge in R whose label is a leader contributes at most one to the count of h 0v for at most one v in R. The sum of h 0v over all internal nodes v is bounded by the number of edges e whose label is a leader. By Lemma 6.2, this is O(n/ log2 n). LEMMA 6.5.

The sum of sv0 over all internal nodes v is at most O(n/log n).

PROOF. Let v be an internal node of R and let u be the child of v with the biggest subtree. sv0 is the number of big segments in the critical sets of visible labels of the subtrees rooted at the children of v other than u. By Lemma 6.3, sv0 is bounded by the sum of the number of visible edges e in Rw , over all children w 6= u of v, such that the label of e is a leader. Note that any edge e = (x, y) whose label is a leader contributes a count to sz0 for some ancestor z of x only if e does not reside in the biggest subtree rooted at the children of z. Suppose such an edge e contributes a count to the ancestors z 1 , z 2 , . . . , z k , in order, on the path from x to the root of R. The size of Rzi+1 is at least double the size of Rzi for all i = 1, 2, . . . , k − 1. Since the size of Rzk is bounded by n, k is at most log n. Any edge e whose label is a leader can contribute a count to sz0 for at most log n ancestors z of x. Therefore, the sum of sv0 over all internal nodes v of R is bounded by log n times the number label is a leader. By Lemma 6.2, the latter is O(n/log2 n). P 0 of edges in R whose 2 v sv = O(log n · (n/log n)) = O(n/log n). 6.2. The Data Structure Hybrid. In this section we describe a data structure, called Hybrid, for managing a set of keys in the range from 1 to n. It supports the operations Member, Predecessor, Successor, Insert, and Delete in O(1) time for keys < log2 n and in O(log n) time for keys ≥ log2 n. Hybrid stores the small keys and the big keys separately. For the latter, it uses a balanced search tree and the operations involving big keys costs O(log n) time. In the following, we see how the constant time operations can be achieved for the small keys in the range [1..(log2 n − 1)].

32

T. W. Lam and F. L. Yue

Let b = dlog ne and let w be a word of b bits. We use wi to denote the ith bit of w, i.e., w = wb−1 wb−2 · · · w1 w0 . To represent a set of “small” keys, Hybrid maintains a b-bit word P and an array of b-bit words Q[0..(b − 1)]. Initially, the set is empty and we set P to zero. The array Q is left uninitialized. For a small key k, k is in the range [1..(b2 − 1)] and k can be written as (k1 b + k2 ) for some k1 , k2 ∈ [0..(b − 1)]. If k is in the set, the k1 th bit of P and the k2 th bit of Q[k1 ] are both set to 1. So the operations Member, Insert, and Delete can be done in constant time. To support the operations Predecessor and Successor efficiently, we assume that two tables PSO[0..(2b − 1)] and PLO[0..(2b − 1)] have been precomputed. For any integer word w of b-bits PSO[w] gives the position of the smallest index i such that wi = 1 while PLO[W ] gives the position of the largest index i such that wi = 1. If w = 0, we assume that both PSO[w] and PLO[w] return −1. With table PSO, we compute the successor of a key k = k1 b + k2 as follows: w := Q[k1 ] with the bits at positions 0, 1, . . . , k2 set to zero; i := PSO[w]; if i ≥ 0 then return (k1 b + i); w := P with the bits at positions 0, 1, . . . , k1 set to zero; j := PSO[w]; if j ≥ 0 then i := PSO[Q[ j]]; return ( jb + i); else return (0); {There is no key with value > k.} The predecessor of a key can be computed similarly with table PLO. It remains to show how tables PSO and PLO can be computed using O(2b ) (i.e., O(n)) time. Observing that for any i ∈ [0..(b − 1)], PSO[w] = i if and only if the least i significant bits of w are all zeros, we compute PSO[0..(2b − 1)] as follows: PSO[0] := −1; for i := 0 to b − 1 do {Initialize all the entries with PSO value equal to i.} for k := 0 to 2b−i−1 do w := (2 ∗ k + 1) ∗ 2i ; PSO[W ] := i; Table PLO can be computed similarly in O(n) time.

References [1]

H. L. Bodlaender, J. S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. M¨uller, and Zs. Tuza, Rankings of graphs, SIAM J. Discrete Math., 11(1) (1998), 168–181. [2] H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms, 18 (1995), 238–255. [3] P. de la Torre, R. Greenlaw, and A. A. Sch¨affer, Optimal edge ranking of trees in polynomial time, Algorithmica, 13 (1995), 529–618. [4] J. S. Deogun, and Y. Peng, Edge ranking of trees, Congr. Numer., 79 (1990), 19–28. [5] A. V. Iyer, H. D. Ratliff, and G. Vijayan, Optimal node ranking of trees, Inform. Process. Lett., 28 (1988), 225–229. [6] A. V. Iyer, H. D. Ratliff, and G. Vijayan, On an edge ranking problem of trees and graphs, Discrete Appl. Math., 30 (1991), 43–52.

Optimal Edge Ranking of Trees in Linear Time [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]

[18]

33

M. Katchalski, W. McCuaig, and S. Seager, Ordered colourings, Discrete Math., 142 (1995), 141–154. T. W. Lam and F. L. Yue, Edge ranking of graphs is hard, Discrete Appl. Math., 85 (1998), 71–86. C. E. Leiserson, Area Efficient Graph Layouts for VLSI, ACM Doctor. Diss. Awards, MIT Press, Cambridge, Massachusetts, 1983. H. R. Lewis and L. Denenberg, Data Structures and Their Algorithms, Harper Collins, New York, 1991, pp. 136–138. J. W. H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl., 11 (1990), 134–172. D. C. Llewellyn, C. Tovey, and M. Trick, Local optimization on graphs, Discrete Appl. Math., 23 (1989), 157–178. A. Pothen, The Complexity of Optimal Elimination Trees, Technical Report CS-88-13, The Pennsylvania State University, 1988. A. A. Sch¨affer, Optimal node ranking of trees in linear time, Inform. Process. Lett., 33 (1989/90), 91–96. J. D. Ullman, Computational Aspects of VLSI, Computer Science Press, Rockville, Maryland, 1984. X. Zhou, M. A. Kashem, and T. Nishizeki, Generalized edge-rankings of trees, IEICE Trans. Fund. Electron., Commun. Comput. Sci., 81-A-2 (1998), 310–320. X. Zhou and T. Nishizeki, An efficient algorithm for edge-ranking trees, in Proc. of the 2nd European Symposium on Algorithms, Lecture Notes in Computer Science, volume 855, Springer-Verlag, Berlin, 1994, pp. 118–129. X. Zhou and T. Nishizeki, Finding optimal edge-rankings of trees, in Proc. of the Sixth Annual ACM– SIAM Symposium on Discrete Algorithms, 1995, pp. 122–131.