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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1994/03/25
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
transmission number, NP-complete problem,
Full Text: PDF>>
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.