Eingang zum Volltext in SciDok
Lizenz
Report (Bericht) zugänglich unter
Algorithms for routing in planar graphs
URN: urn:nbn:de:bsz:291-scidok-41523
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4152/
Quelle:
(1984) Saarbrücken, 1984
pdf-Format:
Dokument 1.pdf (3.697 KB)
Institut:
DDC-Sachgruppe:
Informatik
Dokumentart:
Report (Bericht)
Schriftenreihe:
Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Bandnummer:
1984/07
Sprache:
Englisch
Erstellungsjahr:
1984
Publikationsdatum:
02.09.2011
Kurzfassung auf Englisch:
We present algorithms for solving routing problems for two-terminal nets in planar graphs. Our algorithms run in time O(n2) for general planar graphs and in time O(bn) for grid graphs where n is the number of vertices and b is the number of vertices on the boundary of the infinite face.
Lizenz:
Standard-Veröffentlichungsvertrag