About this Event
2461 SW Campus Way, Corvallis, OR 97331
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. Relying on these structures, we design (i) an (efficient) polynomial time approximation scheme (PTAS) for two different variants of the traveling salesperson problem (TSP) and (ii) simple local search PTASes for r-dominating set and feedback vertex set problems. We then present several results concerning structures of planar graphs. Specifically, we make progresses on two conjectures on existence of large induced forests in planar graphs.
Major Advisor Glencora Borradaile
Committee: Amir Nayyeri
Committee: Mike Rosulek
Committee: Christian Wulff-Nilsen
GCR: Clayton Petsche
Event Details
See Who Is Interested
0 people are interested in this event
User Activity
No recent activity