Realization Problems of a Tree with a Tranamission Number Sequence

Kaoru WATANABE; Masakazu SENGOKU; Hiroshi TAMURA; Yoshio YAMAGUCHI

Realization Problems of a Tree with a Tranamission Number Sequence

Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Yoshio YAMAGUCHI

Full Text Views

0

Cite this

Summary :

Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S ²).Next we consider the d₂-transmission number sequence so that the distance function is defined by a special convex function.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.3 pp.527-533

Publication Date: 1994/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)

Category: Graphs, Networks and Matroids

Cite this

Copy

Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Yoshio YAMAGUCHI, "Realization Problems of a Tree with a Tranamission Number Sequence" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 3, pp. 527-533, March 1994, doi: .
Abstract: Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S ²).Next we consider the d₂-transmission number sequence so that the distance function is defined by a special convex function.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_3_527/_p

Copy

@ARTICLE{e77-a_3_527,
author={Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Yoshio YAMAGUCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Realization Problems of a Tree with a Tranamission Number Sequence},
year={1994},
volume={E77-A},
number={3},
pages={527-533},
abstract={Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S ²).Next we consider the d₂-transmission number sequence so that the distance function is defined by a special convex function.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Realization Problems of a Tree with a Tranamission Number Sequence
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 527
EP - 533
AU - Kaoru WATANABE
AU - Masakazu SENGOKU
AU - Hiroshi TAMURA
AU - Yoshio YAMAGUCHI
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1994
AB - Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S ²).Next we consider the d₂-transmission number sequence so that the distance function is defined by a special convex function.
ER -