<p>You can even get $O(|V|)$ time if the edge weights are sorted. See the following paper:</p>

<p>Erik D. Demaine, Gad Landau, and Oren Weimann, “On Cartesian Trees and Range Minimum Queries”, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 341–353.</p>

CC BY-SA 3.0
2016-03-04T18:24:26.520Z
It's also linear if the tree is a path, using older constructions of the Cartesian tree.
David Eppstein
CC BY-SA 3.0
2016-03-04T16:15:25.880Z
2016-03-04T16:15:25.880Z
Chao Xu
<p>Consider a weighted tree $T = (V,E)$. The <em>bottleneck weight</em> for a pair of vertices $v_1,v_2 \in V$ is the highest weight of the edges on the unique path from $v_1$ to $v_2$ (if $v_1 = v_2$ it is 0). Clearly, using a simple graph traversal from a given node we can find the bottleneck weight from that node to all other nodes in $\mathcal O(|V|)$ time, so we can find all $V^2$ bottleneck weights in $\mathcal O(|V|^2)$ time. </p>

<p>I am interested in the situation where $V$ is large, and we are not interested in finding bottlenecks for all pairs $(v_1,v_2)$, but nonetheless for an (also large) number of pairs $Q$ (the letter $Q$ stands for queries).</p>

<p>I am wondering whether it is possible to do some preprocessing in less than $\mathcal O(|V|^2)$ time -- in particular, in $\mathcal O(|V|\log|V|)$ -- so that we produce some search mechanism, which will then produce a bottleneck weight for $(v_1,v_2)$ in $\mathcal O(\log |V|)$ time. Then we can produce the answer to all queries in $\mathcal O(|V|\log |V| + Q\log|V|)$.</p>

<p>Note that there are $\mathcal O(|V|)$ edges, and thus also that many possible answers to a query. Hence, a balanced decision tree whose leaves are the edge weights, which takes pairs of vertices and decides the highest weight edge between them -- if such a tree exists -- would do the job.</p>

<p>One attempt to build the tree was as follows: recursively split the original tree by removing the highest weight edge. Assign the nodes of the tree indices so that both resulting trees have indices in a contiguous range. Then make a node in the decision tree, which when given two vertices decides whether they lie in the same of the two ranges; if not, this search tree node represents the highest weight edge between the vertices; if so, continue in either of the children of the search tree node.</p>

<p>Unfortunately, this construction fails as the decision tree need not be balanced. Consider, for example, the tree which is just a simple path with ever decreasing weights along the path. Balancing the tree does not seem to be an option, as the decision procedures created by the balancing operations grow too fast (traversing the tree would take too long).</p>

<p>Any suggestions or insights are welcome.</p>

<graph-algorithms><time-complexity>
Efficient all pair bottleneck computation for a tree
Mees de Vries
# Efficient all pair bottleneck computation for a tree

(Asked by: username_0 on 2016-03-04)

Consider a weighted tree $T = (V,E)$. The *bottleneck weight* for a pair of vertices $v\_1,v\_2 \in V$ is the highest weight of the edges on the unique path from $v\_1$ to $v\_2$ (if $v\_1 = v\_2$ it is 0). Clearly, using a simple graph traversal from a given node we can find the bottleneck weight from that node to all other nodes in $\mathcal O(|V|)$ time, so we can find all $V^2$ bottleneck weights in $\mathcal O(|V|^2)$ time.

I am interested in the situation where $V$ is large, and we are not interested in finding bottlenecks for all pairs $(v\_1,v\_2)$, but nonetheless for an (also large) number of pairs $Q$ (the letter $Q$ stands for queries).

I am wondering whether it is possible to do some preprocessing in less than $\mathcal O(|V|^2)$ time -- in particular, in $\mathcal O(|V|\log|V|)$ -- so that we produce some search mechanism, which will then produce a bottleneck weight for $(v\_1,v\_2)$ in $\mathcal O(\log |V|)$ time. Then we can produce the answer to all queries in $\mathcal O(|V|\log |V| + Q\log|V|)$.

Note that there are $\mathcal O(|V|)$ edges, and thus also that many possible answers to a query. Hence, a balanced decision tree whose leaves are the edge weights, which takes pairs of vertices and decides the highest weight edge between them -- if such a tree exists -- would do the job.

One attempt to build the tree was as follows: recursively split the original tree by removing the highest weight edge. Assign the nodes of the tree indices so that both resulting trees have indices in a contiguous range. Then make a node in the decision tree, which when given two vertices decides whether they lie in the same of the two ranges; if not, this search tree node represents the highest weight edge between the vertices; if so, continue in either of the children of the search tree node.

Unfortunately, this construction fails as the decision tree need not be balanced. Consider, for example, the tree which is just a simple path with ever decreasing weights along the path. Balancing the tree does not seem to be an option, as the decision procedures created by the balancing operations grow too fast (traversing the tree would take too long).

Any suggestions or insights are welcome.

**Tags:** graph-algorithms, time-complexity

---

## 1 answers

### Answer by username_1 on 2016-03-04. Score: 4 | Accepted answer

You can even get $O(|V|)$ time if the edge weights are sorted. See the following paper:

Erik D. Demaine, Gad Landau, and Oren Weimann, “On Cartesian Trees and Range Minimum Queries”, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 341–353.

> **Comments:**
> **username_2**: It's also linear if the tree is a path, using older constructions of the Cartesian tree.  

---

