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