Let $G(V, E)$ be an undirected weighted (positive) graph. Given a path $s-t$ find the path that minimizes the maximum weight of any of its edges. This is the minimax path problem.

It is know that a minimum spanning tree $T$ of $G$ gives a minimax path between every pair of nodes. After calculating the MST I want to be able to query any pair of nodes and get the "heaviest" edge of the path in the tree. Ideally I would like to preprocess the MST in linear time and query in constant time.

Wikipedia provide a $O(1)$ lookup with Cartesian trees (preprocess in linear time) and lowest common ancestor but I don't understand it.

Any ideas?

  • 1
    $\begingroup$ You mention that Wikipedia already has a solution – perhaps you should try to understand it? $\endgroup$ – Yuval Filmus Jan 10 '17 at 19:34
  • $\begingroup$ Indeed. But I don't quite get it and tried a lot. Also I would like to know if there are other approaches. Thanks! $\endgroup$ – Laxmana Jan 10 '17 at 19:36
  • $\begingroup$ What specifically don't you understand in Wikipedia's solution? $\endgroup$ – Raphael Jan 10 '17 at 21:50
  • $\begingroup$ I don't understand how you construct the tree. I understand that you start with the heaviest edge and put it to the root but I am confused what you do next. Also how leaves of the Cartesian tree represent the vertices of the Graph? The previous nodes are the weights of the edges right? $\endgroup$ – Laxmana Jan 11 '17 at 10:40
  • $\begingroup$ Also, although I understand why you put it on hold I believe that my question is clear. I am not asking an explanation on the wikipedia article. I am asking for approaches and ideas for the problem. Ie it could be done with BFS/DFS. I provided Wikipedia as a reference. $\endgroup$ – Laxmana Jan 11 '17 at 10:43