6 citations · 7 across the 5 of their papers we have counts for
6 papers
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…
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…
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…