Graduate Thesis Or Dissertation
 

Structural Results and Approximation Algorithms in Minor-free Graphs

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/d217qv924

Descriptions

Attribute NameValues
Creator
Abstract
  • 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.
License
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language
Embargo reason
  • Ongoing Research
Embargo date range
  • 2018-06-10 to 2019-07-11

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details LeHungV2018.pdf 2018-06-10 Public Download