Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 5 of 5 for “"Tree Augmentation"”.
-
An Empirical Analysis of Approximation Algorithms for the Unweighted Tree Augmentation Problem
… study of approximation algorithms for the tree augmentation problem (TAP). TAP is a fundamental problem in network design. The goal of TAP is to add the minimum number of edges from a given edge set to a tree so that it becomes 2-edge connected. Formally, given a tree T = (V, E), where V …
-
Decomposition-based methods for Connectivity Augmentation Problems
… study approximation algorithms for Connectivity Augmentation and related problems. In the Connectivity Augmentation problem, one is given a base graph G=(V,E) that is k-edge-connected, and an additional set of edges $L \subseteq V\times V$ that we refer to as links. The task is to find a minimum …
-
Habitat selection, movement, and home range of largemouth bass (Micropterus salmoides) following a habitat enhancement project in Table Rock Lake, Missouri
Over 2,000 augmentation structures (trees, stumps, and rock piles) have been distributed throughout Table Rock Lake, Missouri. Our objectives were to determine habitat selection, movement, and home range of largemouth bass (Micropterus salmoides). Seventy largemouth bass (>380 mm) were implanted …
-
Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations
… Traveling Salesman Problem (ATSP) and unweighted Tree Augmentation Problem, respectively, in the framework of the SA system and the Las system. For ATSP, our focus is on negative results. For any fixed integer t>=0 and small \epsilon, 0<\epsilon<<1, we prove that the integrality ratio for level t …
-
Augmenting Trees to Achieve 2-Node-Connectivity
This thesis focuses on the Node-Connectivity Tree Augmentation Problem (NC-TAP), formally defined as follows. The first input of the problem is a graph G which has vertex set V and edge set E. We require |V| >= 3 to avoid degenerate cases. The edge set E is a disjoint union of two sets T and L …