1
$\begingroup$

I need an $O(|V||E|)$ algorithm to detect if a graph has a minimum spanning tree with diameter 3.

This paper mentions that it is possible for any diameter by finding the vertex 1-center which can be done using Floyd's algorithm, but I need something much simpler only for the case of diameter 3.

$\endgroup$
2
  • 1
    $\begingroup$ If a tree has diameter 3 then it is either a star or two stars "fused together", i.e. two vertices $x,y$ connected by an edge, so that all other vertex is connected by an edge to either $x$ or $y$. Does that help? $\endgroup$ May 20, 2021 at 11:48
  • $\begingroup$ Thanks allot! Obviously this solves it... In this case all is needed is to find the MST, and then see if the tree which contain all edges of x and y weights the same... $\endgroup$
    – Avi Tal
    May 20, 2021 at 12:12

1 Answer 1

1
$\begingroup$

Perhaps the following helps:

If a tree has diameter 3 then either it is a single vertex, or there are two neighboring vertices $x,y$ such that every other vertex is a neighbor of either $x$ or $y$.

To see why this is true, consider a tree of diameter 3 with more than one vertex. If all vertices have degree 1, then the tree is of that form. Otherwise, let $x$ be a vertex of degree at least 2. If all neighbors of $x$ have degree 1, then you can designate one of them as $y$ and get the above structure. If $x$ has two different neighbors $y,z$ of degree at least 2 then the diameter is at least 4 (a neighbor $y' \neq x$ of $y$ is at distance 4 form a neighbor $z' \neq x$ of $z$), which is impossible. Therefore $x$ has a single neighbor $y$ of degree at least 2. Every vertex is thus either a neighbor of $x$ or a neighbor of $y$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.