By vamaddur, history, 10 months ago, ,

I know how to find the diameter of a tree in linear time, prove the validity of the algorithm used to do so (successive BFS's), and prove why it doesn't work for non-tree connected graphs.

However, I need an algorithm/approach that has better complexity than O(N^2) to find the diameter of a relatively large WEIGHTED pseudotree (a tree with one extra edge).

•
• +4
•

 » 10 months ago, # | ← Rev. 2 →   +27 Pseudotree is basically a single cycle with trees attached to its vertexes. Find the cycle with DFS. You run usual DFS and when it finds edge going to an already visited vertex (and not previous vertex) — here is the cycle. Decompose pseudo tree in cycle and trees. Answer either goes through cycle's edges or not. If it does not, it's completely inside some tree. If it does, then it starts in the deepest leaf of one tree and ends in the deepest leaf of another tree. The first part is the problem you already know how to solve: find diameter of the tree. The second part is more tricky. It can be reformulated as follows: you have an array of K elements, where ai is the depth of i-th tree. You have to find such i and j that ai + a + j + min(|i - j|, K - |i - j|) is maximized. The last problem can be solved with improved brute force: run down i and assume that corresponding j can be found on the right of i (i.e. between i + 1 and something like ). Now you have a bunch of requests of the form "find maximal j + aj on this subsegment". It can be solved with arbitrary RMQ solution. That would result if for the whole solution.
•  » » 10 months ago, # ^ |   0 How would I decompose the pseudotree cycle into trees?
•  » » » 10 months ago, # ^ |   0 After you find the cycle, remove its edges from the graph (e.g. mark its edges are "shall not go here"). You're left with a forest, its components of connectivity are trees growing from the cycle (some trees may be degenerate — i.e. containing a single vertex only).
•  » » » » 10 months ago, # ^ |   0 @yeputons I see! Then step 5 is finding the diameter of each tree in the new forest?
•  » » » » » 10 months ago, # ^ |   0 Yes, exactly. I'm sorry if that wasn't clear from my initial message.
•  » » 10 months ago, # ^ | ← Rev. 3 →   0 Nevermind, my solution was wrong.