6 citations · 9 across the 8 of their papers we have counts for
9 papers
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…
Approximation Complexity of Max-Cut on Power Law Graphs
Mikael Gast, Mathias Hauptmann, Marek Karpinski
In this paper we study the MAX-CUT problem on power law graphs (PLGs) with power law exponent . We prove some new approximability results on that problem. In particular we show…
On Alternation and the Union Theorem
Mathias Hauptmann
Under the assumption , we prove a new variant of the Union Theorem of McCreight and Meyer for the class . This yields a union function which is computable in ti…
Approximability of TSP on Power Law Graphs
Mikael Gast, Mathias Hauptmann, Marek Karpinski
In this paper we study the special case of Graphic TSP where the underlying graph is a power law graph (PLG). We give a refined analysis of some of the current best approximation a…
On the Approximability of Independent Set Problem on Power Law Graphs
Mathias Hauptmann, Marek Karpinski
We give the first nonconstant lower bounds for the approximability of the Independent Set Problem on the Power Law Graphs. These bounds are of the form in the case when the p…
Inapproximability of Dominating Set in Power Law Graphs
Mikael Gast, Mathias Hauptmann, Marek Karpinski
We give logarithmic lower bounds for the approximability of the Minimum Dominating Set problem in connected (alpha,beta)-Power Law Graphs. We give also a best up to now upper appro…
Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations
Mikael Gast, Mathias Hauptmann, Marek Karpinski
We prove new explicit inapproximability results for the Vertex Cover Problem on the Power Law Graphs and some functional generalizations of that class of graphs. Our results depend…
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…
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…