Hey liebe Community,
Aufgabe:
wir haben einen ungerichteten Graphen G=(V,E) gegeben und wir wollen ein maximales Independent Set I mit folgendem Algorithmus finden (siehe Foto)
Ich möchte zeigen, dass der Algorithmus maximal-grad-approximativ ist. Wie kann ich dann zeigen, dass $$|I|\geq \frac{Opt}{max-degree}$$ gilt.
Problem/Ansatz:
Meine erste Idee wäre es $|V|$ als eine obere Schranke für $$Opt$$ zu setzen ($$\Rightarrow |V|\geq Opt$$).
Wäre cool, wenn mir da jemand helfen könnte. :-)
Wenn ich Hilfe aus anderen Foren erhalten habe, werde ich diese Links hier gerne posten.
