查看文章

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 (n log n) 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 (n log n) to O (n) .