Graduate Thesis Or Dissertation

 

Approximation Schemes in Planar Graphs Público Deposited

Contenido Descargable

Descargar 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
Fecha de Emisión
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Conference Name
Academic Affiliation
Subject
Declaración de derechos
Funding Statement (additional comments about funding)
  • My work is supported by the National Science Foundation under Grant No. CCF-1252833.
Publisher
Peer Reviewed
Language

Relaciones

Parents:

This work has no parents.

En Collection:

Elementos