0
$\begingroup$

As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.

This must be done in linear time.

The problem states that the graph is undirected when passed to the algorithm, yet there is a way to transform it into a rooted directed tree graph in linear time.

All the solutions I've seen are using DFS in combination with a dynamic programming-ish approach to solve in linear time, yet I was wondering if there is a purely DP/greedy apporach which will yield linear time?

I've tried to approach this in several ways but it always comes down to either a double BFS algorithm, or DP using DFS.

An algorithm that came to mind:

1. randomly choose a vertex (x), transform the undirected tree into a rooted directed tree
2. give each node it's distance from x , also remember the node with max distance (y).
3. transform the tree to be rooted from y 
4. perform step 2 on y, save the new max in z
5. return distance between y and z

This algorithm will run in $O(n)$, I'm just not sure this implements some (or if any) sort of dp/greedy logic, plain tree traversal.

$\endgroup$
2
  • $\begingroup$ Could you motivate the reason why you don't want to use a (perfectly correct and efficient) BFS? $\endgroup$
    – Nathaniel
    Commented Nov 26, 2022 at 11:34
  • $\begingroup$ This is part of a problem sheet I'm solving, unfortunately I'm constrained to solving using only dynamic programming/greedy approaches. $\endgroup$
    – Aishgadol
    Commented Nov 26, 2022 at 11:37

0

Your Answer

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