A single source shortest path algorithm for graphs with separators
Autor: | B. H. Schmidt, Kurt Mehlhorn |
---|---|
Rok vydání: | 1983 |
Předmět: | |
Zdroj: | Foundations of Computation Theory ISBN: 9783540126898 |
Popis: | We show how to solve a single source shortest path problem on a planar network in time O(n3/2log n). The algorithm works for arbitrary edge weights (positive and negative) and is based on the planar separator theorem. More generally, the algorithm works in time O(na+blog n + n3a+ nd) on graphs G=(V, E) which have a separator of size na, have at most nb edges and where the separator can be found in time nd. |
Databáze: | OpenAIRE |
Externí odkaz: |