Time-dependent shortest paths in treelike graphs Public Deposited

http://ir.library.oregonstate.edu/concern/undergraduate_thesis_or_projects/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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Advisor
Non-Academic Affiliation
Keyword
Rights Statement
Funding Statement (additional comments about funding)
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2016-04-13T15:08:17Z (GMT). No. of bitstreams: 2 license_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: 2 license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5) ShirleyMorganF2016.pdf: 278321 bytes, checksum: 59135f36f07c1da00028e15e24505fc8 (MD5)
  • description.provenance : Submitted by Morgan Shirley (shirlemo@oregonstate.edu) on 2016-04-12T18:39:04Z No. of bitstreams: 2 license_rdf: 1370 bytes, checksum: cd1af5ab51bcc7a5280cf305303530e9 (MD5) ShirleyMorganF2016.pdf: 278321 bytes, checksum: 59135f36f07c1da00028e15e24505fc8 (MD5)

Relationships

In Administrative Set:
Last modified: 07/27/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items