A linear-time algorithm for constructing an optimal node-search strategy of a tree

Sheng Lung Peng; Chin Wen Ho; Tsan Sheng Hsu; Ming Tat Ko; Chuan Yi Tang

doi:10.1007/3-540-68535-9_32

A linear-time algorithm for constructing an optimal node-search strategy of a tree

Sheng Lung Peng, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko, Chuan Yi Tang

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Scopus citations

Abstract

Ellis et al., proposed algorithms (in terms of vertexsep aration) to compute the node-search number of an n-vertextree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.

Original language	English
Title of host publication	Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings
Editors	Wen-Lian Hsu, Ming-Yang Kao
Publisher	Springer Verlag
Pages	279-289
Number of pages	11
ISBN (Print)	3540648240, 9783540648246
DOIs	https://doi.org/10.1007/3-540-68535-9_32
State	Published - 1998
Event	4th Annual International Computing and Combinatorics Conference, COCOON 1998 - Taipei, Taiwan Duration: 12 Aug 1998 → 14 Aug 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1449
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th Annual International Computing and Combinatorics Conference, COCOON 1998
Country/Territory	Taiwan
City	Taipei
Period	12/08/98 → 14/08/98

Access to Document

10.1007/3-540-68535-9_32

Cite this

Peng, S. L., Ho, C. W., Hsu, T. S., Ko, M. T., & Tang, C. Y. (1998). A linear-time algorithm for constructing an optimal node-search strategy of a tree. In W.-L. Hsu, & M.-Y. Kao (Eds.), Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings (pp. 279-289). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1449). Springer Verlag. https://doi.org/10.1007/3-540-68535-9_32

Peng, Sheng Lung ; Ho, Chin Wen ; Hsu, Tsan Sheng et al. / A linear-time algorithm for constructing an optimal node-search strategy of a tree. Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings. editor / Wen-Lian Hsu ; Ming-Yang Kao. Springer Verlag, 1998. pp. 279-289 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4880c539226842fe95163ceee2575f48,

title = "A linear-time algorithm for constructing an optimal node-search strategy of a tree",

abstract = "Ellis et al., proposed algorithms (in terms of vertexsep aration) to compute the node-search number of an n-vertextree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.",

author = "Peng, {Sheng Lung} and Ho, {Chin Wen} and Hsu, {Tsan Sheng} and Ko, {Ming Tat} and Tang, {Chuan Yi}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; 4th Annual International Computing and Combinatorics Conference, COCOON 1998 ; Conference date: 12-08-1998 Through 14-08-1998",

year = "1998",

doi = "10.1007/3-540-68535-9_32",

language = "???core.languages.en_GB???",

isbn = "3540648240",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "279--289",

editor = "Wen-Lian Hsu and Ming-Yang Kao",

booktitle = "Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings",

}

Peng, SL, Ho, CW, Hsu, TS, Ko, MT & Tang, CY 1998, A linear-time algorithm for constructing an optimal node-search strategy of a tree. in W-L Hsu & M-Y Kao (eds), Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1449, Springer Verlag, pp. 279-289, 4th Annual International Computing and Combinatorics Conference, COCOON 1998, Taipei, Taiwan, 12/08/98. https://doi.org/10.1007/3-540-68535-9_32

A linear-time algorithm for constructing an optimal node-search strategy of a tree. / Peng, Sheng Lung; Ho, Chin Wen; Hsu, Tsan Sheng et al.
Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings. ed. / Wen-Lian Hsu; Ming-Yang Kao. Springer Verlag, 1998. p. 279-289 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1449).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A linear-time algorithm for constructing an optimal node-search strategy of a tree

AU - Peng, Sheng Lung

AU - Ho, Chin Wen

AU - Hsu, Tsan Sheng

AU - Ko, Ming Tat

AU - Tang, Chuan Yi

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998.

PY - 1998

Y1 - 1998

N2 - Ellis et al., proposed algorithms (in terms of vertexsep aration) to compute the node-search number of an n-vertextree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.

AB - Ellis et al., proposed algorithms (in terms of vertexsep aration) to compute the node-search number of an n-vertextree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.

UR - http://www.scopus.com/inward/record.url?scp=84948987908&partnerID=8YFLogxK

U2 - 10.1007/3-540-68535-9_32

DO - 10.1007/3-540-68535-9_32

M3 - 會議論文篇章

AN - SCOPUS:84948987908

SN - 3540648240

SN - 9783540648246

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 279

EP - 289

BT - Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings

A2 - Hsu, Wen-Lian

A2 - Kao, Ming-Yang

PB - Springer Verlag

T2 - 4th Annual International Computing and Combinatorics Conference, COCOON 1998

Y2 - 12 August 1998 through 14 August 1998

ER -

Peng SL, Ho CW, Hsu TS, Ko MT, Tang CY. A linear-time algorithm for constructing an optimal node-search strategy of a tree. In Hsu WL, Kao MY, editors, Computing and Combinatorics - 4th Annual International Conference COCOON 1998, Proceedings. Springer Verlag. 1998. p. 279-289. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-68535-9_32

A linear-time algorithm for constructing an optimal node-search strategy of a tree

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this