Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2015 Copyright 2015 University of Bonn, Department of Computer Science, Abt. V
85355

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V