1
$\begingroup$

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...

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

You may not be able to decrease the diameter at all with a single cut, for example for the Y-shaped tree (Mercedes sign-shaped tree). At any rate in order to decrease the diameter you will have to deal with the midpoint of the tree (midpoint of the longest imbedded path). It seems the number of edges you will have to remove depends on the valence at the midpoint (or adjacent vertices).

Improve this answer
$\endgroup$
7
  • $\begingroup$ I know, But the problem is that I can remove only one edge. I'll explain with a very simple tree. Suppose to have a tree with 8 nodes number from 0 to 7, 7 edges, and it's a line. The diameter will be 7 of course. But suppose to remove the edge (2,3), and set a new edge (1,5). In that case, the diameter will be 5. $\endgroup$
    – IceMan990
    Commented Apr 15, 2013 at 9:31
  • $\begingroup$ I am not sure how you mean to formalize the question. Are you looking for a procedure that has best success "on the average"? $\endgroup$
    – Mikhail Katz
    Commented Apr 15, 2013 at 9:34
  • $\begingroup$ Yes, because my procedure works only in some cases... $\endgroup$
    – IceMan990
    Commented Apr 15, 2013 at 9:36
  • $\begingroup$ My hunch is that your algorithm still has to look for the midpoint (center) of tree, and having found it, try to do as best it can. $\endgroup$
    – Mikhail Katz
    Commented Apr 15, 2013 at 11:36
  • $\begingroup$ I've made it, But that approach is not perfect with generic tree...Thanks for your help :) $\endgroup$
    – IceMan990
    Commented Apr 15, 2013 at 12:08
1
$\begingroup$

The diameter of a tree is the length of a longest path, so to reduce the diameter you must remove an edge from each longest path. Find the center by repeatedly removing all the leaves until only one or two vertices are left (BFS is a terrible way to do it). If the center is an edge, removing that reduces the diameter. If the center is a vertex, you need to remove some edges incident to that vertex. Every longest path passes through the center. You need to remove enough edges incident to the center so that one edge from each longest path is included; it could be anything from one edge to all but one of the edges incident to the center.

Improve this answer
$\endgroup$
0
$\begingroup$

It is a real possibility that you will not be able to change the diameter by changing one edge. I think this is an efficient best possible procedure for doing what you can.

Find the diameter and center by repeatedly removing all leaves. Either the diameter is odd and the center is an edge or the diameter is even and the center is a vertex.

When the diameter is odd consider the tree one step before (of diameter 3), if it is anything other than a path you can't decrease the diameter. Otherwise, delete the central edge, this results in two trees of even diameter. Find the center of each and connect those with an edge.

If the diameter is even then there is a central vertex and the tree one step before has diameter 2. If it is a path of length two, delete one of those two edges from the starting tree, then proceed as above, otherwise you again can not decrease the diameter by changing one edge.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .