التفاصيل البيبلوغرافية
| العنوان: |
Small Stretch Spanners on Dynamic Graphs. |
| المؤلفون: |
Brodal, Gerth Stølting, Leonardi, Stefano, Ausiello, Giorgio, Franciosa, Paolo G., Italiano, Giuseppe F. |
| المصدر: |
Algorithms - ESA 2005; 2005, p532-543, 12p |
| مستخلص: |
We present fully dynamic algorithms for maintaining 3- and 5-spanners of undirected graphs. For unweighted graphs we maintain a 3- or 5-spanner under insertions and deletions of edges in O(n) amortized time per operation over a sequence of Ω(n) updates. The maintained 3-spanner (resp., 5-spanner) has O(n3/2) edges (resp., O(n4/3) edges), which is known to be optimal. On weighted graphs with d different edge cost values, we maintain a 3- or 5-spanner in O(n) amortized time per operation over a sequence of Ω(d · n) updates. The maintained 3-spanner (resp., 5-spanner) has O(d · n3/2) edges (resp., O(d · n4/3) edges). The same approach can be extended to graphs with real-valued edge costs in the range [1,C]. All our algorithms are deterministic and are substantially faster than recomputing a spanner from scratch after each update. [ABSTRACT FROM AUTHOR] |
|
Copyright of Algorithms - ESA 2005 is the property of Springer eBooks and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Supplemental Index |