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>>
Buy this Article


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.