Publication
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
Volume/pages
p. 203-210
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
External links
Record
Identification
Creation 14.01.2014
Last edited 21.11.2016