|
For Full-Text 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.E77-A
No.3
pp.527-533 Publication Date: 1994/03/25 Online ISSN:
DOI: Print ISSN: 0916-8508 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, NP-complete problem,
Full Text: PDF>>
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 2).Next we consider the d2-transmission number sequence so that the distance function is defined by a special convex function.
|
|