6 citations · 9 across the 8 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015
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…
cs.DS2015
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…