Self-Adjusting Top Trees

被引:0
|
作者
Tarjan, Robert E. [1 ]
Werneck, Renato F. [1 ]
机构
[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA
来源
PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2005年
关键词
MAXIMUM-FLOW PROBLEM; NETWORK SIMPLEX ALGORITHM; DYNAMIC TREES; SEARCH-TREES; SPANNING-TREES; TIME;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The dynamic trees problem is that of maintaining a forest that changes over tune through edge insertions and deletions. We can associate data with vertices or edges, and manipulate this data individually or in bulk, with operations that deal with whole paths or trees. Efficient solutions to this problem have numerous applications, particularly in algorithms for network flows and dynamic graphs in general. Several data structures capable of logarithmic-time dynamic tree operations have been proposed. The first was Sleator and Tarjan's ST-tree [16, 17] which represents a partition of the tree into paths. Although reasonably fast in practice, adapting ST-trees to different applications is nontrivial. "ropology trees [9], top trees [3], and RC-trees ill are based on tree contractions: they progressively combine vertices or edges to obtain a hierarchical representation of the tree. This approach is more flexible in theory, but all known implementations assume the trees have bounded degree; arbitrary trees are supported only after ternarization. We show how these two approaches can be combined (with very little overhead) to produce a data structure that is as generic as any other, very easy to adapt, and as practical as ST-trees.
引用
收藏
页码:813 / 822
页数:10
相关论文
共 50 条
  • [41] Compiling self-adjusting programs with continuations
    Ley-Wild, Ruy
    Fluet, Matthew
    Acar, Umut A.
    ACM SIGPLAN NOTICES, 2008, 43 (09) : 321 - 333
  • [42] Locally Self-Adjusting Skip Graphs
    Huq, Sikder
    Ghosh, Sukumar
    2017 IEEE 37TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS (ICDCS 2017), 2017, : 805 - 815
  • [43] Self-adjusting mobility management strategy
    Zhu, Yi-Hua
    Gao, Ji
    Zhou, Gen-Gui
    Jisuanji Yanjiu yu Fazhan/Computer Research and Development, 2002, 39 (06):
  • [44] TUBE DRAWING ON SELF-ADJUSTING MANDREL
    ERMANOK, MZ
    GANETS, FM
    SLAVIN, VB
    LEONTEV, YS
    DEMENSHI.VP
    POTOPAEV, AP
    STAL IN ENGLISH-USSR, 1965, (02): : 132 - &
  • [45] A Cost Semantics for Self-Adjusting Computation
    Ley-Wild, Ruy
    Acar, Umut A.
    Fluet, Matthew
    ACM SIGPLAN NOTICES, 2009, 44 (01) : 186 - 199
  • [46] SELF-ADJUSTING HASH-TABLES
    PAGLI, L
    INFORMATION PROCESSING LETTERS, 1985, 21 (01) : 23 - 25
  • [47] A consistent semantics of self-adjusting computation
    Acar, Umut A.
    Blume, Matthias
    Donham, Jacob
    JOURNAL OF FUNCTIONAL PROGRAMMING, 2013, 23 (03) : 249 - 292
  • [48] Distributed Self-Adjusting Tree Networks
    Peres, Bruna Soares
    Souza, Otavio Augusto de Oliveira
    Goussevskaia, Olga
    Avin, Chen
    Schmid, Stefan
    IEEE TRANSACTIONS ON CLOUD COMPUTING, 2023, 11 (01) : 716 - 729
  • [49] Memory Management for Self-Adjusting Computation
    Hammer, Matthew A.
    Acar, Umut A.
    ISMM'08: PROCEEDINGS OF THE 2008 INTERNATIONAL SYMPOSIUM ON MEMORY MANAGEMENT, 2008, : 51 - 60
  • [50] SYNTHESIS OF COMPUTATIONAL SELF-ADJUSTING SYSTEMS
    SOLODOVN.VV
    SEMENOV, VV
    ENGINEERING CYBERNETICS, 1965, (02): : 102 - &