SHORTEST-PATH COMPUTATIONS IN SOURCE-DEPLANARIZED GRAPHS

Authors
FREDERICKSON GN HAMBRUSCH SE TU HY
Citation
Gn. Frederickson et al., SHORTEST-PATH COMPUTATIONS IN SOURCE-DEPLANARIZED GRAPHS, Information processing letters, 47(2), 1993, pp. 71-75
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
47
Issue
2
Year of publication
1993
Pages
71 - 75
Database
ISI
SICI code
0020-0190(1993)47:2<71:SCISG>2.0.ZU;2-Q
Abstract
We consider a class of non-planar graphs that arises in VLSI layout co mpaction and show that a number of shortest path problems on these gra phs can be solved in the same time as the corresponding problem in a p lanar graph.