Feedback Arc Set

Feedback Arc Set

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:

FAS := \{(G=(V,E),~k) | G ist gerichter Graph und enthält eine Kantenmenge E' \subset E: |E'| \leq k so dass gilt: G = (V,EE') ist azyklisch}

Für ungerichtete Graphen existiert eine analoge Definition.

Komplexität

Das Entscheidungsproblem FAS ist für gerichtete Graphen NP-Vollständig, in ungerichteten Graphen hingegen korrespondiert es zu dem Problem, einen minimalen Spannbaum zu finden, was in polynomieller Zeit möglich ist, das heißt, FAS ist in der Komplexitätsklasse P.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Feedback arc set — In graph theory, a directed graph may contain directed cycles, a one way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to… …   Wikipedia

  • Feedback Vertex Set — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) …   Deutsch Wikipedia

  • Feedback vertex set — In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.… …   Wikipedia

  • Feedback (disambiguation) — Feedback is information about actions returned to the source of the actions. To request for feedback on new articles and major edits go .Feedback may also refer to: * Positive feedback, a feedback system that responds to perturbation in the same… …   Wikipedia

  • Hitting-Set-Problem — Das Hitting Set Problem ist ein NP vollständiges Problem aus der Mengentheorie. Es gehört zur Liste der 21 klassischen NP vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. Gegeben ist eine… …   Deutsch Wikipedia

  • Arc (album) — Infobox Album | Name = Arc Type = Live album Artist = Neil Young Released = 1991 Recorded = 1991 North American tour Genre = Noise rock Computer music Electronic music Length = 35:00 Label = Reprise/Warner Bros. Records 26769 Producer = Neil… …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • Karps 21 NP-vollständige Probleme — Eines der bedeutendsten Resultate der Komplexitätstheorie ist der von Stephen Cook im Jahr 1971 erbrachte Nachweis, dass das Erfüllbarkeitsproblem der Aussagenlogik (meist nur kurz SAT genannt) NP vollständig ist. 1972 griff Richard Karp diese… …   Deutsch Wikipedia

  • 21 problemes NP-complets de Karp — 21 problèmes NP complets de Karp Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes… …   Wikipédia en Français

  • 21 problèmes NP-complets de Karp — Les 21 problèmes NP complets de Karp ont marqué une étape importante de l histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”