Dynamischer Graphenalgorithmus gesucht

Singularity2020 · Newbie Anmeldungsdatum: 15.08.2007 Beiträge: 2

Hi, ich suche im Rahmen einer wissenschaftlichen Arbeit nach einem Algorithmus für folgendes Problem:

Gegeben:
ein gerichteter Graph G=(V,E)
ein fester Startknoten s in V

Fragestellung:
Sei v ein beliebiger Knoten in V, gibt es einen Pfad von s nach v?
Nach einem initialen Algorithmus soll diese Fragestellung in konstanter Zeit für jedes v zu beantworten sein (trivial).

Gesucht ist ein voll-dynamischer Graphenalgorithmus, der den Graph nach Entfernen und Hinzufügen einer beliebigen Anzahl von Kanten aktualisiert und wieder obige Fragestellung ermöglicht ohne den initialen Algo komplett erneut auszuführen.
Ist ein solcher Algorithmus bekannt oder zumindest einer, der diese Problemstellung enthält?

brabe · Verfasst am: 15 Aug 2007 - 23:39:12 Titel:

Welche Vorlesung ist das denn?

Mathe-Freak · Full Member Anmeldungsdatum: 02.07.2007 Beiträge: 227

Ich schätze mal, das ist "Graphentheorie"

http://de.wikipedia.org/wiki/Graphentheorie

Hab aber auch keine Ahnung von dieser Materie

brabe · Verfasst am: 15 Aug 2007 - 23:44:45 Titel:

Das habe ich auch nur gefunden. Aber mit Algebra und Topologie kannste mich ganz schnell verlocken mich abzumelden Wink

Daher wollte ich halt wissen, welche Vorlesung Graphentheorie beinhaltet

cyrix42 · Verfasst am: 15 Aug 2007 - 23:47:36 Titel:

Naja, ich würde den Spaß eher einer typischen Algorithmen-Vorlesung der theoretischen Informatik zuordnen...

btw: Der Thread-Autor hat die gleiche Frage auch auf dem Mathe-Planeten gestellt: http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=86114

Cyrix

brabe · Verfasst am: 15 Aug 2007 - 23:55:46 Titel:

Beitrag No.2, vom Themenstarter, eingetragen 2007-08-15 17:50

Hmm, man könnte entweder den Hinweis geben, oder aber zumindest weitere informationen liefern. So den Thread einfach unangetastet lassen finde ich schade

daher danke cyrix42, dann wissen wir woran wir sind.
Ich wollte halt wie immer ein wenig bei den 0 Antworten Thread rumposten, damit keiner sich vernachlässigt fühlt.

Umehrlich zu sein, finde ich den Text auch ein wenig zu schwach formuliert. Liegt wohl daran, dass ich mich damit gar nicht Auskenne. Aber eventuell hätte man helfen können, wenn mehr Text da gewesen wäre, um das Problem besser analysieren zu können. Alleine die Angabe der Vorlesung wäre schon mal hilfreich gewesen
Wink

wobei wir dann wieder beim Thema wären *Titel* Laughing

Singularity2020 · Newbie Anmeldungsdatum: 15.08.2007 Beiträge: 2

Hi! Die Thematik ist genau so in keiner mir bekannten Vorlesung behandelt worden. Aber eine Vorlesung aus der Algorithmik mit Schwerpunkt Graphentheorie trifft's wohl am besten. Wozu ich den Algorithmus dann genau brauche, würde wahrscheinlich zu weit führen, daher hab ich die Beschreibung abstrakt gelassen.

Ich suche lediglich Hinweise aus der Literatur, die auf einen solchen Algorithmus hindeuten. Bisher bin ich hierauf gestoßen, aber das trifft es noch nicht so ganz:

http://www.diku.dk/PATH05/biblio-dynpaths.pdf
http://www.dis.uniroma1.it/~demetres/docs/jacm-tc.pdf
http://www.cs.tau.ac.il/~liamr/papers/roditty.pdf