Search Constraints

Start Over
Filtering by: Contributor Menge, Bruce A. Remove constraint Contributor: Menge, Bruce A. Advisor Borradaile, Glencora Remove constraint Advisor: Borradaile, Glencora Committee Member Tadepalli, Prasad Remove constraint Committee Member: Tadepalli, Prasad

Search Results

  • Approximation Schemes in Planar Graphs

    Creator:
    Zheng, Baigong
    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...
    Resource Type:
    Dissertation
    Full Text:
    the first PTAS results, and for the last problem, we give a PTAS result based on local search and a