Back
2026INF002.pdf
Doctoral thesis

Approximation algorithms for connectivity problems

  • 2026

PhD: Università della Svizzera italiana

Theoretical computer science
Approximation algorithms
Graph theory
Connectivity
Survivable network design
English Graph connectivity is the fundamental measure of robustness in a network. Consequently, it plays a central role in the design of reliable networks, an area with many practical applications. In particular, significant research has focused on the design of cost-efficient networks that can withstand failures or attacks, i.e., networks that stay connected after the removal of some of their elements. This class of problems falls into the category of survivable network design problems. Most survivable network design problems are NP-hard, thus, no efficient algorithm is known to solve them exactly. In light of this, efficient heuristics are often designed for these problems. The goal of approximation algorithms is to design heuristics and provide a rigorous analysis of their performance. In this thesis we study approximation algorithms for connectivity problems. Specifically, we focus on the $2$-edge-connected spanning subgraph problem and the $2$-vertex-connected spanning subgraph problem. We say that a graph $G$ is $2$-edge-connected (resp., $2$-vertex-connected) if it is connected and the removal of one edge (resp., one vertex) does not disconnect the graph. In the $2$-edge-connected spanning subgraph problem (resp., $2$-vertex-connected spanning subgraph problem) we are given a graph $G=(V, E)$ and we want to find a minimum cardinality subset $S\subseteq E$ such that $(V, S)$ is $2$-edge-connected (resp., $2$-vertex-connected). The main contribution of this thesis is to improve upon the state-of-the-art of the aforementioned problems, in terms of approximation algorithms. To do so we use techniques based on the well-known maximum matching problem, and study problems related to matchings that are interesting on their own. We also present in this thesis results in the latter area.
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1334875
Statistics
Document views: 0 File downloads:
  • 2026INF002.pdf: 0