Skip to main content

Computational study on a branch decomposition based exact distance oracle for planar graphs

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2017-10-19
Authors/Contributors
Author: Wei, Xinjing
Abstract
We present a simple exact distance oracle for the point-to-point shortest distance problem in planar graphs. Given an edge weighted planar graph G of n vertices, we decompose G into subgraphs by a branch-decomposition of G, compute the shortest distances between each vertex in a subgraph and the vertices in the boundary of the subgraph, and keep the shortest distances in the oracle. Let bw(G) be the branchwidth of G. Our oracle has O(bw(G)) query time, O(bw(G)n log(n)) size and O(n^2 log(n)) pre-processing time. Computational studies show that our oracle is much faster than Dijkstra’s algorithm for answering point-to-point shortest distance queries for several classes of planar graphs.
Document
Identifier
etd10422
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
Download file Size
etd10422_XWei.pdf 669.97 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0