Back to search

University of Waterloo

Augmenting Trees to Achieve 2-Node-Connectivity

Abstract

dc:description.abstract

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 where the subgraph (V,T) is connected and acyclic. We call the edges in T the tree edges and the edges in L are called links. The second input is a vector c in R^L, c >= 0 (a vector of nonnegative real numbers indexed by the links), which is called the cost of the links. We often refer to this graph G and cost vector c as an instance of NC-TAP. Given an instance G = (V, T U L) and c to NC-TAP, a feasible solution to that instance is a set of links F such that the graph (V, T U F) is 2-connected. The cost of a set of links. The goal of NC-TAP is to find a feasible solution F^* to the given instance such that the the cost of F^* is minimum among all feasible solutions to the instance. This thesis is mainly expository and it has two goals. First, we present the current best-known algorithms for NC-TAP. The second goal of this thesis is to explore new directions in the study of NC-TAP in the last chapter. This is an exploratory chapter where the goal is to use the state of the art techniques for TAP to develop an algorithm for NC-TAP which has an approximation guarantee better than factor 2.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Grout, Logan
Advisor dc:contributor.advisor
  • Cheriyan, Joseph

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/16229

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Grout, Logan. Augmenting Trees to Achieve 2-Node-Connectivity. University of Waterloo, 2020. http://hdl.handle.net/10012/16229