Distance oracles for planar graphs

Resource type
Thesis type
(Thesis) Ph.D.
Date created
2019-11-22
Authors/Contributors
Author: Xu, Gengchun
Abstract
The shortest distance/path problems in planar graphs are among the most fundamental problems in graph algorithms and have numerous new applications in areas such as intelligent transportation systems which expect to get a real time answer or a distance query in large networks. A major new approach to address the new challenges is distance oracles which keep the pre-computed distance information in a data structure (called oracle) and provide an answer for a distance query with the assistance of the oracle. The preprocessing time, oracle size and query time are major criteria for evaluating two-phase algorithms. In this thesis, we first briefly review the previous work and introduce some preliminary results on exact and approximate distance oracles. Then we present our research contributions, which includes improving the preprocessing time for exact distance oracles for planar graphs with small branchwidth and providing the first constant query time (1+\epsilon)-approximate distance oracle with nearly linear size and preprocessing time for planar graphs.
Document
Identifier
etd20592
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Gu, Qianping
Member of collection
Attachment Size
etd20592.pdf 968.08 KB