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