Time-dependent shortest paths in treelike graphs Public

http://ir.library.oregonstate.edu/concern/honors_college_theses/8049g726x

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Non-Academic Affiliation
Rights Statement
Funding Statement (additional comments about funding)
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Submitted by Morgan Shirley (shirlemo@oregonstate.edu) on 2016-04-12T18:39:04ZNo. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2016.pdf: 278321 bytes, checksum: 59135f36f07c1da00028e15e24505fc8 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2016-04-13T15:08:17Z (GMT) No. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2016.pdf: 278321 bytes, checksum: 59135f36f07c1da00028e15e24505fc8 (MD5)
  • description.provenance : Made available in DSpace on 2016-04-13T15:08:17Z (GMT). No. of bitstreams: 2license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5)ShirleyMorganF2016.pdf: 278321 bytes, checksum: 59135f36f07c1da00028e15e24505fc8 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items