1 citations · 1 across the 3 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2022
Randomized Approximation Schemes for the Tutte Polynomial and Random Clustering in Subdense and Superdense Graphs
Mathias Hauptmann, Ronja Tiling
Extending the work of Alon, Frieze abnd Welsh, we show that there are randomized polynomial time approximation schemes for computing the Tutte polynomial in subdense graphs with an…
cs.DS2012
Efficient Parallel Computation of Nearest Neighbor Interchange Distances
Mikael Gast, Mathias Hauptmann
The nni-distance is a well-known distance measure for phylogenetic trees. We construct an efficient parallel approximation algorithm for the nni-distance in the CRCW-PRAM model run…
cs.DS2012★ 1 cited
Approximability of the Vertex Cover Problem in Power Law Graphs
Mikael Gast, Mathias Hauptmann
In this paper we construct an approximation algorithm for the Minimum Vertex Cover Problem (Min-VC) with an expected approximation ratio of 2-f(beta) for random Power Law Graphs (P…