USING LOCAL ADAPTATIONS TO RECONFIGURE A SPANNING TREE OF A NETWORK

We define the notion of a local adaptation of a spanning tree in a bic onnected graph, and consider the number of local adaptations required to reconfigure the spanning tree. We show that inverted right perpendi cular n/2 inverted left perpendicular inverted right perpendicular n/2 - 1 inverted left perpendicular/2 local adaptations are sufficient, a nd may be necessary, to make a node a leaf in the spanning tree, that n2/8 + o(n2) local adaptations are sufficient, and may be necessary, t o add or delete an edge from the spanning tree, and that 3n2/4 + o(n2) local adaptations are sufficient to transform one spanning tree to an other spanning tree.