|
|
| |
| 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
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |