zbMATH — the first resource for mathematics

Approximate distance oracle in \(O(n ^{2})\) time and \(O(n)\) space for chordal graphs. (English) Zbl 1432.68104
Rahman, M. Sohel (ed.) et al., WALCOM: algorithms and computation. 9th international workshop, WALCOM 2015, Dhaka, Bangladesh, February 26–28, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 8973, 89-100 (2015).
Summary: We preprocess a given unweighted chordal graph \(G\) on \(n\) vertices in \(O(n ^{2})\) time to build a data structure of \(O(n)\) size such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices \(u _{i},u _{j} \in V(G)\), \(1 \leq i,j \leq n\), we take constant time to output a distance value \(d _{ij} \leq 2d _{G}(u _{i},u _{j}) + 8\) using our data structure, where \(d _{G}\) is the distance between \(u _{i}\) and \(u _{j}\) in \(G\). In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in \(O(n ^{2.373})\) time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We design an efficient data structure which additively approximates (error of +3) these minimum hitting sets of cliques for all the paths in the clique tree. This data structure is then integrated with an efficient data structure which answers LCA queries in rooted trees to yield our distance oracle for the given chordal graph.
For the entire collection see [Zbl 1305.68028].
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
Full Text: DOI