Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Approximating independent set in perturbed graphs

: Manthey, B.; Plociennik, K.


Faigle, U.:
9th Cologne/Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010. Special Issue : Cologne, Germany, between the 25th and the 27th of May, 2010
Amsterdam: Elsevier, 2013 (Discrete applied mathematics 161.2013, Nr.12)
Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW) <9, 2010, Cologne>
Conference Paper, Journal Article
Fraunhofer ITWM ()

For the maximum independent set problem, strong inapproximability bounds for worst-case efficient algorithms exist. We give a deterministic algorithm beating these bounds, with polynomial expected running-time for semi-random graphs: an adversary chooses a graph with n vertices, and then edges are flipped with a probability of epsilon. Our algorithm guarantees an approximation ratio of Omikron(root of n epsilon) for sufficiently large epsilon .