Edge and node searching problems on trees

In this paper, we consider the edge searching and node searching problems o n 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 n umber of a tree, and improve the running time of a previous algorithm for c onstructing an optimal edge-search strategy of an n-vertex tree from O(nlog n) to O(n). We also improve the running time of a previous algorithm for co nstructing an optimal min-cut linear layout of an n-vertex tree with the ma ximum degree 3 from O(nlogn) to O(n). (C) 2000 Published by Elsevier Scienc e B.V. All rights reserved.