IEICE TRANSACTIONS on Fundamentals
Generalized Edge-Rankings of Trees
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.2 pp.310-320
- Publication Date
- 1998/02/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Xiao ZHOU, Md. Abul KASHEM, Takao NISHIZEKI, "Generalized Edge-Rankings of Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E81-A, no. 2, pp. 310-320, February 1998, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_2_310/_p
Copy
@ARTICLE{e81-a_2_310,
author={Xiao ZHOU, Md. Abul KASHEM, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Edge-Rankings of Trees},
year={1998},
volume={E81-A},
number={2},
pages={310-320},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Generalized Edge-Rankings of Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 310
EP - 320
AU - Xiao ZHOU
AU - Md. Abul KASHEM
AU - Takao NISHIZEKI
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 1998
AB - 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.
ER -
English
