Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Dynamischer Graphenalgorithmus gesucht
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Dynamischer Graphenalgorithmus gesucht
 
Autor Nachricht
Singularity2020
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 15.08.2007
Beiträge: 2

BeitragVerfasst 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
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.10.2005
Beiträge: 2807
Wohnort: Lehrerzimmer

BeitragVerfasst am: 15 Aug 2007 - 22:39:12    Titel:

Welche Vorlesung ist das denn?
Mathe-Freak
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.07.2007
Beiträge: 227

BeitragVerfasst am: 15 Aug 2007 - 22:43:16    Titel:

Ich schätze mal, das ist "Graphentheorie"

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

Hab aber auch keine Ahnung von dieser Materie
brabe
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.10.2005
Beiträge: 2807
Wohnort: Lehrerzimmer

BeitragVerfasst 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 Wink

Daher wollte ich halt wissen, welche Vorlesung Graphentheorie beinhaltet
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24255

BeitragVerfasst am: 15 Aug 2007 - 22: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
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.10.2005
Beiträge: 2807
Wohnort: Lehrerzimmer

BeitragVerfasst 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
Wink

wobei wir dann wieder beim Thema wären *Titel* Laughing
Singularity2020
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 15.08.2007
Beiträge: 2

BeitragVerfasst am: 16 Aug 2007 - 08:33:13    Titel:

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
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Dynamischer Graphenalgorithmus gesucht
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum