9 citations · 19 across the 13 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.DS2025
A Better-Than--Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu
The 2-Edge-Connected Spanning Subgraph Problem (2ECSS) is a fundamental problem in survivable network design. Given an undirected -edge-connected graph, the goal is to find a $2…
cs.DS2025
Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
Felix Hommelsheim
The Forest Augmentation Problem (FAP) asks for a minimum set of additional edges (links) that make a given forest 2-edge-connected while spanning all vertices. A key special case i…
cs.DS2025
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
Felix Hommelsheim, Zhenwei Liu, Nicole Megow +1
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, whi…