|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
G.N. Frederickson. Data structures for on-line updating of minimal spanning trees. SIAM J. Comput., Vol 14:781--798, 1985.
|
| |
3
|
|
| |
4
|
F. Geerts, B. Kuijpers, and J. Van den Bussche. Topological canonization of planar spatial data and its incremental maintenance. In T. Polle, T. Ripke, and K.-D. Schewe, editors, Fundamentals of Information Systems, Kluwer Academic Publishers, 1998, pp 55--68.
|
| |
5
|
F. Geerts, P. Revesz, and J. Van den Bussche. On-line topological simplification of weighted graphs. Technical report, arXiv:cs.DS/0608091. http://arxiv.org/abs/cs.DS/060891
|
| |
6
|
G. Italiano. Dynamic graph algorithms. In Mikhail J. Atallah, editor, Handbook on Algorithms and Theory of Computation, CRC Press, 1998.
|
| |
7
|
|
| |
8
|
K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. EACTS Monographs on Theoretical Computer Science. Springer-Verlag, 1984.
|
 |
9
|
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
E.1