|
Autor |
Nachricht |
Singularity2020 Newbie


Anmeldungsdatum: 15.08.2007 Beiträge: 2
|
Verfasst am: 15 Aug 2007 - 13:18:55 Titel: Dynamischer Graphenalgorithmus gesucht |
|
|
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 Senior Member


Anmeldungsdatum: 26.10.2005 Beiträge: 2807 Wohnort: Lehrerzimmer
|
Verfasst am: 15 Aug 2007 - 22:39:12 Titel: |
|
|
Welche Vorlesung ist das denn? |
|
 |
Mathe-Freak Full Member


Anmeldungsdatum: 02.07.2007 Beiträge: 227
|
|
 |
brabe Senior Member


Anmeldungsdatum: 26.10.2005 Beiträge: 2807 Wohnort: Lehrerzimmer
|
Verfasst am: 15 Aug 2007 - 22:44:45 Titel: |
|
|
Das habe ich auch nur gefunden. Aber mit Algebra und Topologie kannste mich ganz schnell verlocken mich abzumelden
Daher wollte ich halt wissen, welche Vorlesung Graphentheorie beinhaltet |
|
 |
cyrix42 Valued Contributor


 Anmeldungsdatum: 14.08.2006 Beiträge: 24257
|
|
 |
brabe Senior Member


Anmeldungsdatum: 26.10.2005 Beiträge: 2807 Wohnort: Lehrerzimmer
|
Verfasst am: 15 Aug 2007 - 22: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
wobei wir dann wieder beim Thema wären *Titel*  |
|
 |
Singularity2020 Newbie


Anmeldungsdatum: 15.08.2007 Beiträge: 2
|
|
 |
|