An efficient oracle for counting shortest paths in planar graphs

Thesis type
(Thesis) M.Sc.
Date created
2021-08-09
Authors/Contributors
Author: Gong, Ye
Abstract
An O(\sqrt {n}) query time and O(n^{1.5}) size oracle for counting shortest paths is proposed. Given a pair of vertices u and v in a planar graph G of n vertices, the oracle answers the number of shortest paths from u to v in O(\sqrt {n}) time and whether there is a unique shortest path from u to v in O(\log n) time. Bezáková and Searns [ISAAC 2018] give an O(\sqrt {n}) query time and O(n^{1.5}) size oracle for counting shortest paths in planar graphs. Applying this oracle directly, it takes O(\sqrt {n}) time to answer whether there is a unique shortest path from u to v. A key component in our oracle is to apply Voronoi diagrams on planar graphs, which is a recent novel notion used in oracles for answering shortest distance, to speed up the query time. Computational studies show that our oracle is faster to answer queries than the oracle of Bezáková and Searns for large graphs. Our computational studies also confirm that Voronoi diagrams are efficient data structures for shortest distance oracles in practice.
Document
Identifier
etd21503
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Gu, Qianping
Language
English
Member of collection
Attachment Size
input_data\22255\etd21503.pdf 7.13 MB