Approximation von Independent Set mit maximum-degree

24.01.2021, 12:13	RonaldosKuzeng	Auf diesen Beitrag antworten »
Approximation von Independent Set mit maximum-degree Meine Frage: Hey liebe Community, 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 $\begin{eqnarray} \|I\|\geq \frac{Opt}{max-degree} \end{eqnarray}$ gilt. Meine Ideen: Meine erste Idee wäre es $\begin{eqnarray} \|V\| \end{eqnarray}$ als eine obere Schranke für $\begin{eqnarray} Opt \end{eqnarray}$ zu setzen ( $\begin{eqnarray} \Rightarrow \|V\|\geq Opt \end{eqnarray}$ ). 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.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »