Hi! I have an acyclic undirected unweighted connected graph (a tree :) ), and I have to disconnect an edge and create a new one to minimize the diameter. For now, I do a bfs on a arbitrary node, find the furtherest node, start another bfs from this node and I get the diameter in O(2n). One of the neighbor from the node that have distance equals to (diameter+1)/2 is the edge to disconnect. After that, I have two different connected component. So i'll find on both component the node that has lowest diameter, and connect it.

Obviously this solution is not perfect, do you have any hint?

Sorry for my bad english...