DYNAMIC EXPRESSION-TREES

被引:13
作者
COHEN, RF
TAMASSIA, R
机构
[1] Department of Computer Science, Brown University, Providence, 02912-1910, RI
关键词
DYNAMIC ALGORITHM; EXPRESSION EVALUATION; SERIES-PARALLEL DIGRAPH;
D O I
10.1007/BF01190506
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We present a technique for dynamically maintaining a collection of arithmetic expressions represented by binary trees (whose leaves are variables and whose internal nodes are operators). A query operation asks for the value of an expression (associated with the root of a tree). Update operations include changing the value of a variable and combining or decomposing expressions by linking or cutting the corresponding trees. Our dynamic data structure uses linear space and supports queries and updates in logarithmic time. An important application is the dynamic maintenance of maximum flow and shortest path in series-parallel digraphs under a sequence of vertex and edge insertions, series and parallel compositions, and their respective inverses. Queries include reporting the maximum flow or shortest st-path in a series-parallel subgraph.
引用
收藏
页码:245 / 265
页数:21
相关论文
共 30 条
[1]  
Afrati F.N., 1988, CS8807 BROWN U DEP C
[2]  
AUSIELLO G, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P12
[3]   BIASED SEARCH-TREES [J].
BENT, SW ;
SLEATOR, DD ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1985, 14 (03) :545-568
[4]  
BERMAN AM, 1990, ACTA INFORM, V27, P665, DOI 10.1007/BF00259471
[5]  
Brent R. P., 1973, COMPLEXITY SEQUENTIA, P83
[6]   PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].
BRENT, RP .
JOURNAL OF THE ACM, 1974, 21 (02) :201-206
[7]   SHORTEST-PATH ALGORITHMS - TAXONOMY AND ANNOTATION [J].
DEO, N ;
PANG, CY .
NETWORKS, 1984, 14 (02) :275-323
[8]  
DIBATTISTA G, 1989, 30TH P IEEE S F COMP, P436
[9]   MAINTENANCE OF A MINIMUM SPANNING FOREST IN A DYNAMIC PLANE GRAPH [J].
EPPSTEIN, D ;
ITALIANO, GF ;
TAMASSIA, R ;
TARJAN, RE ;
WESTBROOK, J ;
YUNG, M .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1992, 13 (01) :33-54
[10]   A FAST PARAMETRIC MAXIMUM FLOW ALGORITHM AND APPLICATIONS [J].
GALLO, G ;
GRIGORIADIS, MD ;
TARJAN, RE .
SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :30-55