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?


closed as unclear what you're asking by Raphael Jan 10 '17 at 21:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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