Oregon State University



Event Details

PhD Oral Preliminary Examination – Hung Le

Tuesday, June 6, 2017 8:30 AM - 10:30 AM

Structural Results and Approximation Algorithms in Minor-free Graphs
Planarity has been successfully exploited to design faster and more accurate approximation algorithms for many graph optimization problems. The celebrated theorem of Kuratowski completely characterizes planar graphs as those excluding K_5 and K {3,3} as minors. Kuratowski’s theorem allows one to generalize planar graphs to H-minor-free graphs: those that exclude a fixed graph H as a minor. The deep results of Robertson and Seymour reveal many hidden structures in H-minor-free graphs, that have been used extensively in algorithmic designs. In this proposal, we present our results on designing an (efficient) polynomial time approximation scheme (PTAS) for traveling salesperson (TSP), r-dominating set and feedback vertex set problems, all in H-minor-free graphs. We also present our work on the size of induced forests in planar graphs. We then discuss some open problems that arise from our work, and possible techniques to attack them.

Major Advisor: Glencora Borradaile
Committee: Amir Nayyeri
Committee: Christian Wulff-Nilsen
Committee: Mike Rosulek
Committee: Eugene Zhang
GCR: Clayton Petsche

Kelley Engineering Center (campus map)
Calvin Hughes
1 541 737 3168
Calvin.Hughes at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: