imported>PerfektesChaos: tk k

2020-01-27T18:04:46Z

tk k

Neue Seite

Der '''Algorithmus von Walker''' ist ein Reglement zum Zeichnen von [[Baum (Graphentheorie)|Bäumen]] in der [[Graphentheorie]].

Der [[Algorithmus]] basiert auf der geschichteten Zeichnung des Baumes (Layered Drawings). Dabei ergibt sich die Y-Koordinate eines jeden [[Knoten (Graphentheorie)|Knoten]] des Baumes direkt aus der Tiefe des Knotens. Dadurch muss bei diesem Algorithmus nur die X-Koordinate des jeweiligen Knotens in der Zeichnung bestimmt werden.

Die [[Laufzeit (Informatik)#Laufzeit als Dauer der Ausführung|Laufzeit]] des Algorithmus ist, anders als ursprünglich vermutet, nicht linear, sondern quadratisch abhängig von der Anzahl der Knoten. Es existiert jedoch eine Verbesserung des Algorithmus von Christoph Buchheim [[et al.]], der eine lineare Laufzeit ermöglicht.

== Literatur ==
* {{Literatur
|Autor=John Q. Walker
|Titel=A node-positioning algorithm for general trees
|Sammelwerk=Software: Practice and Experience
|Band=20
|Nummer=7
|Datum=1990-07-01
|ISSN=1097-024X
|Seiten=685–705
|DOI=10.1002/spe.4380200705}}
* {{Literatur
|Autor=Christoph Buchheim, Michael Jünger, Sebastian Leipert
|Titel=Improving Walker’s Algorithm to Run in Linear Time
|Sammelwerk=Graph Drawing
|Reihe=Lecture Notes in Computer Science
|Nummer=2528
|Verlag=Springer
|Ort=Berlin / Heidelberg
|Datum=2002
|ISBN=978-3-540-00158-4
|Seiten=344–353
|DOI=10.1007/3-540-36151-0_32}}

[[Kategorie:Algorithmus (Graphentheorie)|Walker, Algorithmus von]]

Algorithmus von Walker - Versionsgeschichte

imported>PerfektesChaos: tk k