IEICE TRANSACTIONS on Fundamentals
Realization Problems of a Tree with a Tranamission Number Sequence
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(
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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(
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(
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(
ER -
English
