Shortest paths in planar graphs with real lengths in O(nlog2n/loglogn) time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Given an n-vertex planar directed graph with real edge lengths and with no negativecycles, we show how to compute single-source shortest path distances in the graph inO(n log2 n/ log log n) time with O(n) space. This is an improvement of a recent time boundof O(n log2 n) by Klein et al.
Original language | English |
---|---|
Title of host publication | Algorithms – ESA 2010 : 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II |
Editors | Mark de Berg, Ulrich Meyer |
Number of pages | 12 |
Volume | Part II |
Publisher | Springer |
Publication date | 2010 |
Pages | 206-217 |
ISBN (Print) | 978-3-642-15780-6 |
ISBN (Electronic) | 978-3-642-15781-3 |
DOIs | |
Publication status | Published - 2010 |
Event | 18th Annual European Symposium on Algorithms - Liverpool, United Kingdom Duration: 6 Sep 2010 → 8 Sep 2010 Conference number: 18 |
Conference
Conference | 18th Annual European Symposium on Algorithms |
---|---|
Nummer | 18 |
Land | United Kingdom |
By | Liverpool |
Periode | 06/09/2010 → 08/09/2010 |
Links
- http://arxiv.org/pdf/0911.4963v1
Submitted manuscript
ID: 172854937