Oregon State University



Event Details

MS Final Examination – Farzad Zafarani

Friday, May 20, 2016 3:00 PM - 5:00 PM

A Structural Theorem for Shortest Vertex-Disjoint Paths Computation in Planar Graphs
Given k terminal pairs (s_1,t_1),(s_2,t_2), ..., (s_k,t_k) in an edge-weighted graph G, the k Shortest Vertex-Disjoint Paths problem is to find a collection P_1, P_2, ..., P_k of vertex-disjoint paths with minimum total length, where P_i is an s_i-to-t_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 bounds the number of crossings between the i'th path of k Shortest Vertex-Disjoint Paths with the i'th path of k-1 Shortest Vertex-Disjoint Paths problem and guarantees that the i'th path of the k Shortest Vertex-Disjoint paths does not cross j'th (j != i) path of the k-1 Vertex-Disjoint Paths problem.

This Structural Theorem can be used to obtain an n^O(k^3) algorithm for the k Shortest Vertex-Disjoint Paths problem.

Co-Major Advisor: Amir Nayyeri
Co-Major Advisor: Glencora Borradaile
Committee: Eugene Zhang
GCR: Abi Farsoni

Milam Hall (campus map)
Nicole Thompson
1 541 737 3617
Nicole.Thompson at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: