Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Improving Walker’s Algorithm to Run in Linear Time

Christoph BuchheimContact Information, Michael JüngerContact Information and Sebastian LeipertContact Information

(6)  Institut für Informatik, Universität zu Köln, Pohligstraße 1, 50969 Köln, Germany
(7)  caesar research center, Friedensplatz 16, 53111 Bonn, Germany
Abstract
The algorithm of Walker [5] is widely used for drawing trees of unbounded degree, and it is widely assumed to run in linear time, as the author claims in his article. But the presented algorithm clearly needs quadraticrun time. We explain the reasons for that and present a revised algorithm that creates the same layouts in linear time.

Contact Information Christoph Buchheim
Email: buchheim@informatik.uni-koeln.de

Contact Information Michael Jünger
Email: mjuenger@informatik.uni-koeln.de

Contact Information Sebastian Leipert
Email: leipert@caesar.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
1 newer article

  1. Mäkinen, Ville-Petteri (2005) High-throughput pedigree drawing. European Journal of Human Genetics 13(8)
    [CrossRef]
Remote Address: 38.107.191.106 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)