7 citations · 31 across the 24 of their papers we have counts for
Showing 2018 · cs.DSShow all
3 papers · 2 filters
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.DS2018
Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast
Markus Chimani, Tilo Wiedera
The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of a given graph such that has maximum edge cardinality. For more than two decades, the only know…
cs.DS2018★ 2 cited
Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments
Markus Chimani, Ivo Hedtke, Tilo Wiedera
Given a graph , the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of with the maximum number of edges. The only known non-trivial exact algorithm utiliz…