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