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.
11.5.3 Minimale dominierende Mengen
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 ...
Get Algorithmische Graphentheorie, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
