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