
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Generalized EdgeRankings of Trees
Xiao ZHOU Md. Abul KASHEM Takao NISHIZEKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E81A
No.2
pp.310320 Publication Date: 1998/02/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: algorithm, edgeranking, tree, separator tree, visible edges,
Full Text: PDF(916.8KB)>>
Summary:
In this paper we newly define a generalized edgeranking of a graph G as follows: for a positive integer c, a cedgeranking 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 cedgeranking of G, that is, a cedgeranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multipart products; it is equivalent to finding a cedgeseparator tree of G having the minimum height. We present an algorithm to find an optimal cedgeranking of a given tree T for any positive integer c in time O(n^{2}log Δ), where n is the number of vertices in T and Δ is the maximum vertexdegree of T. Our algorithm is faster than the best algorithm known for the case c=1.

