Showing cs.DSShow all
2 papers · 1 filter
cs.DS2018
A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs
Stephan Beyer, Markus Chimani, Joachim Spoerhase
We propose a simple and natural approximation algorithm for the problem of finding a 2-edge-connected spanning subgraph of minimum total edge cost in a graph. The algorithm maintai…
cs.DS2014
Strong Steiner Tree Approximations in Practice
Stephan Beyer, Markus Chimani
In this experimental study we consider Steiner tree approximations that guarantee a constant approximation of ratio smaller than . The considered greedy algorithms and approache…