A single source shortest path algorithm for graphs with separators

Autor:	B. H. Schmidt, Kurt Mehlhorn
Rok vydání:	1983
Předmět:	Physics Combinatorics Euclidean shortest path Indifference graph Shortest Path Faster Algorithm Shortest path problem K shortest path routing Planar separator theorem Yen's algorithm Longest path problem MathematicsofComputing_DISCRETEMATHEMATICS
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:	https://explore.openaire.eu/search/publication?articleId=doi_________::fb180d95d4ee4c0e1b3ca025fcc41018 https://doi.org/10.1007/3-540-12689-9_113 Zobrazit plný text záznamu