Gegeben sei ein einfacher, endlicher, ungerichteter Graph G=(V, E) mit Eckenmenge V (G)
und Kantenmenge E (G). Eine unabhängige Menge in G ist eine Teilmenge der
Eckenmenge V (G), in der je zwei Ecken nicht adjazent in G sind. Ein oft untersuchtes
kombinatorisches Optimierungsproblem ist die Frage nach einer unabhängigen Menge
maximaler Kardinalität. Aufgrund der schweren Berechenbarkeit des dazugehörigen
Entscheidungsproblems ist es gerechtfertigt, sich mit Schranken, überwiegend unteren …