
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.

Realization Problems of a Tree with a Tranamission Number Sequence
Kaoru WATANABE Masakazu SENGOKU Hiroshi TAMURA Yoshio YAMAGUCHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E77A
No.3
pp.527533 Publication Date: 1994/03/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on the 6th Karuizawa Workshop on Circuits and Systems) Category: Graphs, Networks and Matroids Keyword: transmission number, NPcomplete problem,
Full Text: PDF>>
Summary:
Problems of realizing a vertexweighted 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 vertexweighted tree. Let S be a sequence whose terms are pairs of a nonnegative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertexweighted tree or not, is called wTNS. We prove that wTNS is NPcomplete, 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 ^{2}).Next we consider the d_{2}transmission number sequence so that the distance function is defined by a special convex function.

