[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Dynamic expression trees

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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 shortestst-path in a series-parallel subgraph.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. F. N. Afrati, D. Q. Goldin, and P. C. Kanellakis. Efficient Parallelism for Structured Data: Directed Reachability in S-P Dags, Technical Report CS-88-07, Department of Computer Science, Brown University, 1988.

  2. B. Alpern, R. Hoover, B. Rosen, P. Sweeney, and F. K. Zadeck. Incremental evaluation of computational circuits,Proc. ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 32–42.

  3. G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, and U. Nanni. Incremental algorithms for minimal length paths,Proc. ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 12–21.

  4. S. W. Bent, D. D. Sleator, and R. E. Tarjan. Biased search trees,SIAM J. Comput.,14 (1985), 545–568.

    Google Scholar 

  5. A. M. Berman, M. C. Paull, and B. G. Ryder. Proving relative lower bounds for incremental algorithms,Acta Inform.,27 (1990), 665–683.

    Google Scholar 

  6. R. P. Brent. The parallel evaluation of arithmetic expressions in logarithmic time, inComplexity of sequential and parallel numerical algorithms, Academic Press, New York, 1973, pp. 83–102.

    Google Scholar 

  7. R. P. Brent, The parallel evaluation of general arithmetic expressions,J. Assoc. Comput. Mach.,21 (1974), 201–206.

    Google Scholar 

  8. M. D. Carrol and B. G. Ryder. Incremental data flow analysis via dominator and attribute updates,Proc. 15th ACM Symp. on Principles of Programming Languages, 1988, pp. 274–284.

  9. N. Deo and C. Pang. Shortest-path algorithms: taxonomy and annotations,Networks,14 (1984), 275–323.

    Google Scholar 

  10. G. Di Battista and R. Tamassia. Incremental planarity testing,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 436–441.

  11. D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic plane graph,J. Algorithms,13 (1992), 33–54.

    Google Scholar 

  12. S. Even and H. Gazit. Updating distances in dynamic graphs,Methods Oper. Res.,49 (1985), 371–387.

    Google Scholar 

  13. G. Gallo, M. Grigoriadis, and R. E. Tarjan. A fast parametric network flow algorithm,SIAM J. Comput.,18 (1989), 30–55.

    Google Scholar 

  14. A. V. Goldberg, E. Tardos, and R. E. Tarjan. Network Flow Algorithms, Technical Report STAN-CS-89-1252, Department of Computer Science, Stanford University, 1989.

  15. M. T. Goodrich. Applying parallel processing techniques to classification problems in constructive solid geometry,Proc. ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 118–128.

  16. D. Gusfield and C. Martel. A Fast Algorithm for the Generalized Parametric Minimum Cut Problem and Applications, Technical Report CSE-89-21, Department of Computer Science and Engineering, University of California, Davis, 1989.

    Google Scholar 

  17. G. F. Italiano, A. Marchetti-Spaccamela, and U. Nanni. Dynamic data structures for series-parallel graphs,Algorithms and Data Structures (Proc. WADS '89), Lecture Notes in Computer Science, Vol. 382, Springer-Verlag, Berlin, 1989, pp. 352–372.

    Google Scholar 

  18. R. M. Karp and V. Ramachandran. A survey of parallel algorithms for shared memory machines, inHandbook of Theoretical Computer Science, Vol. A, Elsevier/MIT Press, Amsterdam/ Cambridge, MA, 1990, pp. 869–942.

    Google Scholar 

  19. E. L. Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints,Ann. Discrete Math.,2 (1978), 75–90.

    Google Scholar 

  20. C. C. Lin and R. C. Chang. On the dynamic shortest path problem,Proc. International Workshop on Discrete Algorithms and Complexity, 1989, pp. 203–212.

  21. W. Pugh and T. Teitelbaum. Incremental computation via function caching,Proc. 16th ACM Symp. on Principles of Programming Languages, 1989, pp. 315–328.

  22. H. Rohnert. A dynamization of the all-pairs least cost problem,Proc. STACS '85, 1985, pp. 279–286.

  23. D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees,J. Comput. Systems Sci.,24 (1983), 362–381.

    Google Scholar 

  24. P. M. Spira and A. Pan. On finding and updating spanning trees and shortest paths,SIAM J. Comput.,4 (1975), 373–380.

    Google Scholar 

  25. L. Stockmeyer. Optimal orientation of cells in slicing floorplan design,Inform. and Control,57 (1983), 91–101.

    Google Scholar 

  26. K. Takamizawa, T. Nishizeki, and N. Saito. Linear time computability of combinatorial problems on series-parallel graphs,J. Assoc. Comput. Mach.,29 (1982), 623–641.

    Google Scholar 

  27. R. Tamassia and F. P. Preparata. Dynamic maintenance of planar digraphs, with applications,Algorithmica,5 (1990), 509–527.

    Google Scholar 

  28. R. E. Tarjan.Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 44, CBMS, Washington, DC, 1983.

    Google Scholar 

  29. J. Valdes, R. E. Tarjan, and E. L. Lawler. The recognition of series-parallel digraphs,SIAM J. Comput.,11 (1982), 298–313.

    Google Scholar 

  30. L. Weinberg. Linear graphs: Theorems, algorithms, and applications, inAspects of Network and System Theory, R. E. Kalman and N. DeClaris, eds., Holt, Rinehart, and Winston, New York, 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA

    R. F. Cohen & R. Tamassia

Authors
  1. R. F. Cohen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Tamassia
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by T. Nishizeki.

Research supported in part by the National Science Foundation under Grant CCR-9007851, by the US Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225, and by Cadre Technologies, Inc.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cohen, R.F., Tamassia, R. Dynamic expression trees. Algorithmica 13, 245–265 (1995). https://doi.org/10.1007/BF01190506

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01190506

Key words

Search

Navigation