Edge and node searching problems on trees

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

研究成果: 雜誌貢獻期刊論文同行評審

18 引文 斯高帕斯(Scopus)

摘要

In this paper, we consider the edge searching and node searching problems on trees. Given a tree, we show a transformation from an optimal node-search strategy to an optimal edge-search strategy. Using our transformation, we simplify a previous linear-time algorithm for determining the edge-search number of a tree, and improve the running time of a previous algorithm for constructing an optimal edge-search strategy of an n-vertex tree from O(nlogn) to O(n). We also improve the running time of a previous algorithm for constructing an optimal min-cut linear layout of an n-vertex tree with the maximum degree 3 from O(nlogn) to O(n).

原文???core.languages.en_GB???
文章編號3389
頁(從 - 到)429-446
頁數18
期刊Theoretical Computer Science
240
發行號2
DOIs
出版狀態已出版 - 2000

指紋

深入研究「Edge and node searching problems on trees」主題。共同形成了獨特的指紋。

引用此