Time-dependent shortest paths in treelike graphs

Honors College Thesis

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/honors_college_theses/8049g726x

Descriptions

Attribute Name	Values
Creator	Shirley, Morgan
Abstract	We present a proof that the number of breakpoints in the arrival function between two terminals in graphs of treewidth ω is n^(O(log²ω) when the edge arrival functions are piecewise linear. This is an improvement on the bound of n^(Θ(log n))by Foschini, Hershberger, and Suri for graphs without any bound on treewidth. We provide an algorithm for calculating this arrival function using star-mesh transformations, a generalization of the wye-delta-wye transformations. Key Words: treewidth, time-dependent shortest paths, star-mesh transformations
License	All rights reserved
Resource Type	Honors College Thesis
Date Available	2016-04-13T15:08:17+00:00
Date Issued	2016-03-11
Degree Level	Bachelor's
Degree Name	Honors Bachelor of Science (H.B.S.)
Degree Field	Computer Science
Degree Grantor	Oregon State University
Commencement Year	2016
Advisor	Borradaile, Glencora
Non-Academic Affiliation	Oregon State University. Honors College
Rights Statement	In Copyright
Funding Statement (additional comments about funding)	NSF Grant No. CCF-1252833.
Publisher	Oregon State University
Peer Reviewed	No
Language	English [eng]
Replaces	http://hdl.handle.net/1957/58670

Parents:

This work has no parents.

In Collection:

Thumbnail	Title	Date Uploaded	Visibility	Actions
	ShirleyMorganF2016.pdf	2017-07-30	Public	Download