4 papers · 1 filter
Improved Approximations for Flexible Network Design
Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanita
Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) f…
Node Connectivity Augmentation of Highly Connected Graphs
Waldo Galvez, Dylan Hyatt-Denesik, Afrouz Jabal Ameli +1
Node-connectivity augmentation is a fundamental network design problem. We are given a -node connected graph together with an additional set of links, and the goal is to add…
Finding Almost Tight Witness Trees
Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanità
This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This…
Node Connectivity Augmentation via Iterative Randomized Rounding
Haris Angelidakis, Dylan Hyatt-Denesik, Laura Sanità
Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements, such as nodes or links. One such problem is Connectivity…