imported>Serpen: Navigationsleiste Karps 21 NP-vollständige Probleme

2020-02-03T11:39:32Z

Navigationsleiste Karps 21 NP-vollständige Probleme

Neue Seite

Der Begriff '''Feedback Arc Set''' stammt aus der [[Graphentheorie]] und bezeichnet eine Menge von Kanten, durch deren Entfernung aus einem Graphen dieser azyklisch, d. h. kreisfrei wird.

== Entscheidungsproblem ==

Das zugehörige Entscheidungsproblem ist wie folgt definiert:

<math>FAS</math> <math>:= \{(G=(V,E),~k) |</math> G ist gerichteter Graph und enthält eine Kantenmenge <math>E' \subset E: |E'| \leq k</math> so dass gilt: <math>G'=(V, E - E')</math> ist azyklisch<math>\}</math>

Für ungerichtete Graphen existiert eine analoge Definition.

== Komplexität ==

Das Entscheidungsproblem FAS ist für gerichtete Graphen [[NP-vollständig]]. In ungerichteten Graphen korrespondiert es zu dem Problem, einen [[Minimaler Spannbaum|minimalen Spannbaum]] zu finden, was in polynomieller Zeit möglich ist, FAS ist dort also in der Komplexitätsklasse '''P'''.

{{Navigationsleiste Karps 21 NP-vollständige Probleme}}

[[Kategorie:Graphentheorie]]
[[Kategorie:Komplexitätstheorie]]

Feedback Arc Set - Versionsgeschichte

imported>Serpen: Navigationsleiste Karps 21 NP-vollständige Probleme