Events Calendar

PhD Final Exam – Baigong Zheng

Approximation Schemes in Planar Graphs

There are growing interests in designing polynomial-time approximation schemes (PTAS) for optimization problems in planar graphs. Many NP-hard problems are shown to admit PTAS in planar graphs in the last decade, including Steiner tree, Steiner forest, two- edge-connected subgraphs and so on. We follow this research line and study several NP- hard problems in planar graphs, including minimum three-vertex-connected spanning subgraph problem, minimum three-edge-connected spanning subgraph problem, relaxed minimum-weight subset three-edge-connected subgraph problem and minimum feedback vertex set problem. For the first three problems, we give the first PTAS results, and for the last problem, we give a PTAS result based on local search and a practical heuristic algorithm that provides a trade-off between running time and solution quality like a PTAS.

Major Advisor: Glencora Borradaile
Committee: Amir Nayyeri
Committee: Mike Rosulek
Committee: Prasad Tadepalli
GCR: Ross Hatton

Wednesday, November 7 at 10:00am to 12:00pm

Kelley Engineering Center, 1007
110 SW Park Terrace, Corvallis, OR 97331

Event Type

Lecture or Presentation

Event Topic

Research

Organization
College of Engineering, Electrical Engineering and Computer Science
Contact Name

Calvin Hughes

Contact Email

Calvin.Hughes@oregonstate.edu

Subscribe
Google Calendar iCal Outlook

Recent Activity