Generalized Edge-Rankings of Trees


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.2   pp.310-320
Publication Date: 1998/02/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
algorithm,  edge-ranking,  tree,  separator tree,  visible edges,  

Full Text: PDF(916.8KB)>>
Buy this Article

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 labeling (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 optimal c-edge-ranking of G, that is, a c-edge-ranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding a c-edge-separator tree of G having the minimum height. We present an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n2log Δ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T. Our algorithm is faster than the best algorithm known for the case c=1.