A Structural Theorem For Shortest Vertex-Disjoint Paths Computation in Planar Graphs Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/hq37vr06r

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Given k terminal pairs (s₁,t₁),(s₂,t₂),..., (s[subscript k],t[subscript k]) in an edge-weighted graph G, the k Shortest Vertex-Disjoint Paths problem is to find a collection P₁, P₂,..., P[subscript k] of vertex-disjoint paths with minimum total length, where P[subscript i] is an s[subscript i]-to-t[subscript i] path. As a special case of the multi-commodity flow problem, computing vertex disjoint paths has found several applications, for example in VLSI design, or network routing. In this thesis we describe a Structural Theorem for a special case of the Shortest Vertex-Disjoint Paths problem in undirected planar graphs where the terminal vertices are on the boundary of the outer face. At a high level, our Structural Theorem guarantees that the i[superscript th] path of the k Shortest Vertex-Disjoint paths does not cross j[superscript th] (j ≠ i) path of the k-1 Vertex-Disjoint Paths problem.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Keyword
Subject
Rights Statement
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Submitted by Farzad Zafarani (zafaranf@onid.orst.edu) on 2016-07-19T02:19:33Z No. of bitstreams: 1 ZafaraniFarzad2016.pdf: 1385139 bytes, checksum: 279d958973a3fe499305848ae5039689 (MD5)
  • description.provenance : Submitted by Farzad Zafarani (zafaranf@onid.orst.edu) on 2016-07-19T17:20:16Z No. of bitstreams: 1 ZafaraniFarzad2016.pdf: 1384798 bytes, checksum: 135d04f32d8ce071cf10a77c6d25e17d (MD5)
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2016-08-09T19:31:44Z (GMT) No. of bitstreams: 1 ZafaraniFarzad2016.pdf: 1384798 bytes, checksum: 135d04f32d8ce071cf10a77c6d25e17d (MD5)
  • description.provenance : Made available in DSpace on 2016-08-09T19:31:44Z (GMT). No. of bitstreams: 1 ZafaraniFarzad2016.pdf: 1384798 bytes, checksum: 135d04f32d8ce071cf10a77c6d25e17d (MD5) Previous issue date: 2016-05-20
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2016-08-09T16:13:51Z (GMT) No. of bitstreams: 1 ZafaraniFarzad2016.pdf: 1384798 bytes, checksum: 135d04f32d8ce071cf10a77c6d25e17d (MD5)
  • description.provenance : Rejected by Julie Kurtz(julie.kurtz@oregonstate.edu), reason: Everything looks good, but since you do not have any algorithms remove the page - LIST OF ALGORITHMS in the pretext pages. Once revised, log back into ScholarsArchive and go to the upload page. Replace the attached file with the revised PDF and resubmit. Thanks, Julie on 2016-07-19T17:08:12Z (GMT)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items