Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2012 Copyright 2012 Universität Bonn, Institut für Informatik, Abt. V
85334

17.12.2012

Inapproximability of Dominating Set in Power Law Graphs
Mikael Gast, Mathias Hauptmann and Marek Karpinski
[Download PostScript] [Download PDF]

We give logarithmic lower bounds for the approximability of the Minimum Dominating Set problem in connected (α,β)-Power Law Graphs. We give also a best up to now upper approximation bound on the problem for the case of the parameters β > 2. We develop also a new functional method for proving lower approximation bounds and display a sharp phase transition between approximability and inapproximability of the underlying problem. This method could also be of independent interest.

Last Change: 11/05/14 at 10:58:28
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope