September 2015
Intermediate to advanced
415 pages
12h 24m
German
Ein weiterer Approximationsalgorithmus mit linearem Aufwand und Wirkungsgrad 2 wird in Aufgabe 47 in Kapitel 9 behandelt. Zur Zeit ist kein Algorithmus mit einem besseren Wirkungsgrad bekannt und es gibt Hinweise, dass ein solcher Algorithmus auch nicht existieren kann.
Eine dominierendeMenge von Ecken eines ungerichteten Graphen G mit Eckenmenge E ist eine Menge D von Ecken, so dass jede Ecke e ∈ E\D zu einer Ecke aus D benachbart ist. Eine dominierende Menge D heißt minimal dominierende Menge, falls es keine dominierende Menge D' mit |D' | < |D| gibt. Die Mächtigkeit einer minimal dominierenden Menge von G heißt Dominationszahl Für einen zusammenhängenden Graphen G gilt trivialerweise
Die Ecken einer Eckenüberdeckung ...