Loading...
Please wait, while we are loading the content...
Similar Documents
Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (1990)
| Content Provider | CiteSeerX |
|---|---|
| Author | Frederickson, Greg N. |
| Abstract | An algorithm is presented for generating a succinct encoding of all pairs shortest path information in an n-vertex directed graph G with O(n) edges. The edges have real-valued costs, but the graph contains no negative cycles. The algorithm runs in O('Y(G)n + ('Y(G))'log 'Y(G)) time, where 'Y(G) is a topological emhedding measure that we define. The algorithm uses a decomposition of the graph into O(-y(G)) outer-planar subgraphs satisfying certain separator properties, and a linear-time algorithm is presented to find this decomposition. |
| File Format | |
| Publisher Date | 1990-01-01 |
| Access Restriction | Open |
| Content Type | Text |
