activity
20122016
most citedImproved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations

6 citations · 7 across the 5 of their papers we have counts for

collaborators
Showing 2016Show all

1 paper · 1 filter

cs.DS2016

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…