X. Zhou et al., GENERALIZED EDGE-RANKINGS OF TREES, IEICE transactions on fundamentals of electronics, communications and computer science, E81A(2), 1998, pp. 310-320
Citations number
15
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
In this paper we newly define a generalized edge-ranking of a graph G
as follows: for a positive integer c, a c-edge ranking of G is a label
ing (ranking) of the edges of G with integers such that, for any label
i, deletion of all edges with labels > i leaves connected components,
each having at most c edges with label i. The problem of finding an o
ptimal c-edge-ranking of G, that is, a c-edge-ranking using the minimu
m number of ranks. has applications in scheduling the manufacture of c
omplex multi-part products; it is equivalent to finding a c-edge-separ
ator tree of G having the minimum height. We present an algorithm to f
ind an optimal c-edge-ranking of a given tree T for any positive integ
er c in time O(n(2) log Delta), where n is the number of vertices in T
and Delta is the maximum vertex-degree of T. Our algorithm is faster
than the best algorithm known For the case c = 1.