Bottleneck Trees and Its Applications in Solving Path Queries Involving Bottleneck Edges

Overview

In many problems such as network routing, the length of a path is often less important than the bottleneck (minimum or maximum edge weight) of the path. In this study, I investigate the applications of Bottleneck Tree while answering bottleneck edge queries. In particular, I show how to compute more complex queries on static graphs, using Bottleneck Trees over the Minimum Spanning Tree of the graph. Among other examples, we can find in $O(log^2n)$ time per query, the minimum bottleneck path cost from node X to any node Y such that Y belongs to [L, R], where X, L, R are given in each query. I also show how to maintain the structure when there are edge additions to the graph, and still answer interesting queries, in $O((n+q)log^2n)$ amortised time complexity, given $q$ queries and edge additions. Finally, I show how to answer simple bottleneck path queries and maintain the minimum spanning tree of a graph under edge additions using Disjoint Set Union Trees, in $O((n+q)logn)$ complexity, given $q$ queries and updates.

Competition history

• ISEF 2020 Systems Software · Entry SOFT034

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.