Graduate Thesis Or Dissertation

 

Approximation Schemes in Planar Graphs Public Deposited

Downloadable Content

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

Descriptions

Attribute NameValues
Creator
Abstract
  • 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.
License
Resource Type
Date Issued
Degree Level
Degree Name
Degree Grantor
Commencement Year
Advisor
Committee Member
Conference Name
Academic Affiliation
Subject
Rights Statement
Funding Statement (additional comments about funding)
  • My work is supported by the National Science Foundation under Grant No. CCF-1252833.
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

In Collection:

Items