We introduce the notion of counting oracles for various path problems in graphs. We present an oracle for counting the number of shortest paths between a pair of vertices in any planar graph which takes O(n^1.5) preprocessing time and space which allows for O(sqrt(n)) time queries for any pair of vertices in the graph. We extend our results to other graph classes which admit small balanced separators and present applications where this oracle improves the best known running time. This research was done at RIT, sponsored by an NSF REU grant, under Dr. Ivona Bezakova.
Ivona Bezáková, & Andrew Searns (2018). On Counting Oracles for Path Problems. In 29th International Symposium on Algorithms and Computation (ISAAC 2018) (pp. 56:1–56:12). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://drops.dagstuhl.de/opus/volltexte/2018/10004/pdf/LIPIcs-ISAAC-2018-56.pdf