Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2015 Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V
89160

11.03.2015

On the Approximability of Independent Set Problem on Power Law Graphs
Mathias Hauptmann and Marek Karpinski
[Download PostScript] [Download PDF]

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 nε in the case when the power law exponent satisfies β <1. In the case when β =1, the lower bound is of the form log (n)ε. The embedding technique used in the proof could also be of independent interest.

Last Change: 03/11/15 at 09:30:07
 English
Universität Bonn -> Institut für Informatik -> Abteilung V