Booth Id:
SOFT034
Category:
Systems Software
Year:
2020
Finalist Names:
Basu, Rajarshi (School: Bodhicariya Senior Secondary School)
Abstract:
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.