Login | Register

Timetable-based Routing in Fixed Schedule Dynamic Networks

Title:

Timetable-based Routing in Fixed Schedule Dynamic Networks

Cristian Oswaldo, Rodriguez Santiago (2021) Timetable-based Routing in Fixed Schedule Dynamic Networks. Masters thesis, Concordia University.

[thumbnail of RodriguezSantiago_MA_S2021.pdf]
Preview
Text (application/pdf)
RodriguezSantiago_MA_S2021.pdf - Accepted Version
Available under License Spectrum Terms of Access.
3MB

Abstract

A fixed schedule dynamic network has a set of nodes (eg. vehicles or satellites) that move using a known schedule and trajectory, so that the connections between nodes in the network appear and disappear in a predictable manner. We study the problem of finding a foremost journey in such a network: given a query time, source and destination node, we find a temporal path that arrives at the earliest time at the destination. We give a new approach to the problem that uses a timetable sorted in order of the start time of connections, and describe three algorithms using this approach. We prove their correctness and give tight bounds on their worst-case time complexities. We also show extensive experimental results that show that our new algorithms outperforms the previous best algorithm given in [21].

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Cristian Oswaldo, Rodriguez Santiago
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:12 March 2021
Thesis Supervisor(s):Lata, Narayanan
ID Code:988127
Deposited By: Cristian Oswaldo Rodriguez Santiago
Deposited On:29 Jun 2021 22:31
Last Modified:29 Jun 2021 22:31
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top