Shortest path computations in source-deplanarized graphs

We consider a class of non-planar graphs that arises in VLSI layout compaction and show that a number of shortest path problems on these graphs can be solved in the same time as the corresponding problem in a planar graph.

Saved in:
Bibliographic Details
Published in:Information processing letters 1993-08, Vol.47 (2), p.71-75
Main Authors: Frederickson, Greg N., Hambrusch, Susanne E., Tu, Hung-Yi
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Analysis of algorithms
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Graphs
Information processing
Operational research and scientific management
Operational research. Management science
planar graphs
shortest paths
Theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a class of non-planar graphs that arises in VLSI layout compaction and show that a number of shortest path problems on these graphs can be solved in the same time as the corresponding problem in a planar graph.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(93)90227-Z