Dynamic fractional cascading (Q908708): Difference between revisions

Let U be an ordered set and let \(G=(V,E)\) be an undirected graph. For each \(v\in V\) there is a set C(v)\(\subseteq U\), the catalogue of v, and for every edge \(e\in E\) there is a range \(R(e)=[7(e),r(e)]\), which is a closed interval in U. \(N=\sum_{v\in V}| C(v)|\) is the total size of the catalogues. The goal is to organize the catalogues in a data structure so that deletion, insertions and queries can be supported efficiently. Chazelle and Guibas introduced fractional cascading as a general data-structuring technique for approaching this kind of problems; however, they provided efficient \(O(n+\log N)\) algorithm for queries only under some restrictions on the graph G. The authors give general algorithms that support queries in time \(0(\log (N+| E|)+n \log \log (N+| E|))\) and deletions and insertions in O(log log(N\(+| E|))\). Detailed analysis and some applications are also given.