Diskussion:Erreichbarkeitsproblem in Graphen

Platzverbrauch O(1)? Ich bin mir nicht sicher, ob der Platzverbrauch wirklich O(1) ist, um einen Knoten zu speichern. Angenommen, man hat n Knoten, die binär codiert werden, dann ist der Platzverbrauch mit O(log(n)) beschränkt.

-- 83.216.231.212 12:12, 16. Jun. 2007 (CEST) Sebastian

Platzverbrauch O(1)? Das ist falsch. Ein Knoten kann nicht von nur einer Zelle gespeichert werden weil dann Eingabealphabet nicht mehr endlich. wäre. Richtig wäre O(log(n)).

Platzverbrauch O(1)? Bin auch der Meinung dass das falsch ist, sonst wäre ja GAP eine reguläre Sprache, denn REG = NSPACE(1)?! (nicht signierter Beitrag von 79.235.164.246 (Diskussion) 18:23, 17. Aug. 2010 (CEST))

AKTUALISIERUNGSBEDARF

Omer Reingold hat 2005 das Problem mit einem Logarithmischen Aufwand lösen können. Dafür erhielt er den Grace Murray Hopper Award. siehe auch hier: http://de.wiki.x.io/wiki/Grace_Murray_Hopper_Award

Verbindung mit en:st-connectivity

Der Artikel ist derzeit mit en:st-connectivity verbunden. Darin geht es aber nur um das Erreichbarkeitsproblem in ungerichteten Graphen, hier aber sowohl um gerichtete als auch ungerichtete. Sollte der Artikel nicht mit en:Reachability verbunden werden? --man (Diskussion) 19:36, 1. Sep. 2024 (CEST)

Bei der einzigen derzeit angegebenen Quelle, Papadimitriou Computational Complexity heißt es REACHABILITY. Nach meinem Eindruck ist Erreichbarkeit der allgemeinere und gebräuchlichere Begriff, vgl. z.B. Allender Reachability Problems, den ich gleich noch in der Literatur ergänze. Ich ändere die Verbindung. --man (Diskussion) 20:39, 10. Sep. 2024 (CEST)