Path Problems in Geographic Information Systems

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Taghinezhad Omran, Masoud




Path problems are among the most widely studied problems in graph theory. Unlike in well-studied conventional static shortest path problems, the characteristics of underlying networks may change over time in many real-world applications. An efficient solution to the Shortest Path problem, should therefore take the dynamics of the underlying graph into consideration. In this thesis, we study a dynamic version of the Shortest Path Problem in which travel times on links of the underlying graph change over time, and present improved and easily implemented exact and approximation algorithms.
theoretical improvements in time-dependent shortest path computation and technical advancements in the provision of real-time traffic data, many travelers these days use and rely on navigation systems and time-dependent shortest path computation in their everyday lives. This may, however, compromise users' privacy since untrusted Location Based Services (LBS) are able to use inference attacks to gain access to sensitive information about users, such as their driving habits, health conditions they may have, their sexual orientation, or details about their lifestyle. In this dissertation,
we propose a heuristic algorithm that protects the privacy of users who submit frequent location based queries to a Location Based Service. Although, shortest paths are preferred in most applications related to navigation and transportation, they can easily be inferred and regenerated, and should therefore be avoided in applications where user security is paramount. For example, a traveling VIP is more concerned about the security of her path rather than its length. We study the traveling VIP problem in which the goal is to randomly select a path from k candidate source-destination paths.
When links are shared between many paths security is compromised and security guards may have to be placed on such links. The number of shared edges, then, should be minimized to reduce the costs associated with security guards who must be assigned to each shared link. We show that this problem is hard to approximate, and propose an approximation algorithm
which has been experimentally evaluated on various networks.


Computer Science
System Science




Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).