Abstract/Details

Faster minimum weight subgraph algorithms


2006 2006

Other formats: Order a copy

Abstract (summary)

In this dissertation we consider combinatorial optimization problems. In particular, we concentrate on algorithms that find subgraphs of a given graph of minimum weight that have a certain specified structure.

First, we consider the problem of finding a minimum weight 2-edge-connected spanning subgraph of a given 2-edge-connected graph. For this problem we provide a linear-time exact algorithm for weighted graphs of bounded treewidth, a linear-time PTAS for unweighted planar graphs, and a PTAS for weighted planar graphs.

Furthermore, we design algorithms for the b-edge dominating set problem. We improve upon an existing 8/3-approximation for general weighted graphs, prove limitations of previously used methods, and give linear-time algorithms for this problem on trees.

Indexing (details)


Subject
Mathematics;
Computer science
Classification
0405: Mathematics
0984: Computer science
Identifier / keyword
Applied sciences; Pure sciences; Approximation; Combinatorial optimization; Linear programming; Minimum weight subgraph; Subgraph algorithms
Title
Faster minimum weight subgraph algorithms
Author
Berger, Andre
Number of pages
84
Publication year
2006
Degree date
2006
School code
0665
Source
DAI-B 67/09, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9780542875861
Advisor
Grigni, Michelangelo; Parekh, Ojas
University/institution
Emory University
University location
United States -- Georgia
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3234002
ProQuest document ID
304941875
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/304941875
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.