|
Title
|
|
|
|
On-line maintenance of simplified weighted graphs for efficient distance queries
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| We give two efficient on-line algorithms to simplify weighted graphs by eliminating degree-two vertices. Our algorithms are on-line---they react to updates on the data, keeping the simplification up-to-date. We provide both analytical and empirical evaluations of the efficiency of our algorithms. We prove an O(log n) upper bound on the amortized time complexity of our maintenance algorithms, with n the number of insertions. One of our algorithms can handle in logarithmic time the deletions of vertices and edges as well. |
| |
|
Language
|
|
|
|
English
| |
|
Source (book)
|
|
|
|
Proceedings of the 14th ACM International Symposium on Geographic Information Systems (ACM-GIS 2006), Arlington, Va, USA, November 10-11, 2006 / By, de, Rolf A. [edit.]; et al.
| |
|
Publication
|
|
|
|
S.l.
:
ACM
,
2006
| |
|
ISBN
|
|
|
|
1-59593-529-0
| |
|
DOI
|
|
|
|
10.1145/1183471.1183505
| |
|
Volume/pages
|
|
|
|
p. 203-210
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|