Honors College Thesis

 

Time-dependent shortest paths in treelike graphs Public

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/honors_college_theses/8049g726x

Descriptions

Attribute NameValues
Creator
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
Resource Type
DOI
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Conference Name
Conference Section/Track
Conference Location
Non-Academic Affiliation
Rights Statement
Funding Statement (additional comments about funding)
  • NSF Grant No. CCF-1252833.
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)
Embargo reason

Relationships

Parents:

This work has no parents.

Items