Incremental computation (incrementalization; finite differencing)

Academic Journals

1. C. Demetrescu, G.F. Italiano. Maintaining dynamic matrices for fully dynamic transitive closure. Algorithmica, 51(4):387-427, 2008.
2. A. Nepomniaschaya. Efficient Implementation of the Italiano Algorithms for Updating the Transitive Closure on Associative Parallel Processors. Fundamenta Informaticae, 89(2):313-329, 2008.
3. M. P\vatra\cscu, C. Tarni\ct\va P\vatra\cscu. On Dynamic Bit-Probe Complexity. Theoretical Computer Science, 380:127-142, 2007.
4. C. Demetrescu, G.F. Italiano. Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures. Journal of Discrete Algorithms, 4(3):353-383, 2006.
5. Dong, Libkin, Wong. Incremental Recomputation in Local Languages. INFCTRL: Information and Computation (formerly Information and Control), 181, 2003.
6. Y.A. Liu. Efficiency by incrementalization: An introduction. Higher-Order and Symbolic Computation, 13(4), 2000.
7. Leonid Libkin, Limsoon Wong. On the Power of Incremental Evaluation in SQL-Like Languages. Lecture Notes in Computer Science, 1949, 2000.
8. Laurent Mauborgne. An Incremental Unique Representation for Regular Trees. Nordic Journal of Computing, 7(4):290-311, 2000.
9. Leonid Libkin, Limsoon Wong. Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. Lecture Notes in Computer Science, 1369:222-0, 1998.
10. David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig. Sparsification-a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. download
11. Lars Baekgaard, Leo Mark. Incremental computation of nested relational query expressions. ACM Trans. Database Syst, 20(2):111-148, 1995. download
12. Annie Liu, Tim Teitelbaum. Systematic derivation of incremental programs. Science of Computer Progamming (SCP), 24:1-39, 1995.
13. Daniel Yellin. Speeding Up Dynamic Transitive Closure for Bounded Degree Graphs. Acta Informatica, Also available as IBM T.J.\ Watson Research Center Research Report, 30:369-384, 1993.
14. X. Qian, G. Wiederhold. Incremental recomputation of active relational expressions. IEEE Transactions on Knowledge and Data Engineering, 3(3):337-341, 1991.
15. R. Paige. Programming with Invariants. IEEE Software, 1986.
16. Herbert Edelsbrunner, Mark H. Overmars. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms, 6(4):515-542, 1985. download download
17. R. Paige, S. Koenig. Finite Differencing of Computable Expressions. ACM TOPLAS, 4(3):402-454, July 1982.

Book Chapters

1. C.D. Zaroliagis. Implementations and Experimental Studies of Dynamic Graph Algorithms. In Experimental algorithmics: From algorithm design to robust and efficient software, Chap. 11, Springer-Verlag New York Inc, 2002.
2. Sadaaki Miyamoto. Fuzzy Multisets and their Generalizations. In Mathematical,Computer Science, and Molecular Computing Points of View, Vol. 2235, Lecture Notes in Computer Science (LNCS), Springer Verlag, 2001. download
3. R. Paige. Applications of Finite Differencing to Database Integrity Control and Query/Transaction Optimization. In Advances in Database Theory, Vol. 2, J. Minker, J. Nicolas, H. Gallaire (eds.), ?, 1984.

International Conferences

1. Michael Nissen. FunSETL for Data Analysis. In 1st 3gERP Workshop, Frederiksberg, Denmark, 2007.
2. Yakov Nekrich. Space efficient dynamic orthogonal range reporting. In Symposium on Computational Geometry, Pages 306-313, 2005. download
3. Yanhong A. Liu, Scott D. Stoller. From datalog rules to efficient programs with time and space guarantees. In PPDP '03: Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, Pages 172-183, New York, NY, USA, 2003. download
4. C. Demetrescu, GF Italiano. Fully dynamic transitive closure: Breaking through the O (n/sup 2/) barrier. In Proc. Foundations of Computer Science (FOCS), 2000.
5. V. King, G. Sagert. A fully dynamic algorithm for maintaining the transitive closure. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, Pages 492-498, 1999.
6. Y.A. Liu. Efficient computation via incremental computation. In Pacific-Asia Conf. on Knowledge Discovery and Data Mining, 1999.
7. D. Frigioni, T. Miller, U. Nanni, G. Pasqualone, G. Schaefer, C. Zaroliagis. An experimental study of dynamic algorithms for directed graphs. In Proc. European Symposium on Algorithms (ESA), 1998.
8. M.R. Henzinger, V. King. Fully dynamic biconnectivity and transitive closure. In Proc. Foundations of Computer Science (FOCS), 1995.
9. Timothy Griffin, Leonid Libkin. Incremental maintenance of views with duplicates. In Proc. of the Int.\ Conference on Management of Data (SIGMOD), M.\ Carey (ed.), Pages 328-339, San Jose, CA, 1995.
10. G. Ramalingam, Thomas Reps. An Incremental Algorithm for Maintaining the Dominator Tree of a Reducible Flowgraph. In Proc. 21st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), Portland, Oregon, January 1994.
11. A. Gupta, I.S. Mumick, VS Subrahmanian. Maintaining views incrementally. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Pages 157-166, 1993.
12. B. Alpern, B. Rosen, P. Sweeney, F. Zadeck. Incremental Evaluation of Computational Circuits. In Proc. 1st Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), San Francisco, California, Pages 32-42, 1990.
13. D. Yellin, R. Strom. INC: a language for incremental computations. In PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, Pages 115-124, New York, NY, USA, 1988. download
14. J. Waltz, G. Johnson. Incremental Evaluation for a General Class of Circular Attribute Grammars. In Proc. SIGPLAN '88 Conf. on Programming Lanuguage Design and Implementation, Pages 209-221, Atlanta, Georgia, June 1988.
15. B. Lang, F. Dupont. Incremental Incrementally Compacting Garbage Collection. In Proc. ACM SIGPLAN '87 Symp. on Interpreters and Interpretive Techniques, St. Paul, Minnesota, June 1987.
16. J. La Poutré, J. van Leeuwen. Maintenance of Transitive Closures and Transitive Reductions of Graphs. In Proc. Int'l Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 314, Pages 106-120, June 1987.
17. P. Wadler. Views: A Way of Pattern Matching to Cohabit with Data Abstraction. In Proc. 14th Annual ACM Symposium on Principles of Programming Languages, Pages 307-313, January 1987.
18. J. Cai, R. Paige. Binding Performance at Language Design Time. In Proc. 14th ACM Symp. on Principles of Programming Languages, Pages 85-97, January 1987.
19. G. Johnson, J. Walz. A Maximum-Flow Approach to Anomaly Isolation in Unification-Based Incremental Type Inference. In Proc. 13th Annual ACM Symp. on Principles of Programming Languages, Pages 44-57, January 1986.
20. Allen Goldberg, Robert Paige. Stream processing. In LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming, Pages 53-62, New York, NY, USA, 1984. download
21. L. Meertens. Incremental Polymorphic Type Checking in B. In Proc. 10th ACM Symp. on Principles of Programming Languages (POPL), Pages 265-275, 1983.

Technical Reports

1. Amihood Amir, Martin Farach, Ramana Idury, Johannes La Poutré, Alejandro Sch\"affer. Improved Dynamic Dictionary Matching. Research Report DIMACS, New Jersey, No 92, July 1992.
2. G. Ramalingam, T. Reps. An Incremental Algorithm for a Generalization of the Shortest-Path Problem. Research Report University of Wisconsin at Madison, No 1087, May 1992.
3. G. Ramalingam, T. Reps. On the Computational Complexity of Incremental Algorithms. Research Report University of Wisconsin at Madison, No 1033, August 1991.
4. D. Yellin. A Dynamic Transitive Closure Algorithm. Research Report IBM T.J. Watson Research Ctr, No 0, June 1988.
5. J. La Poutre, J. van Leeuwen. Maintenance of Transitive Closures and Transitive Reductiosn of Graphs. Research Report Utrecht University, No 0, November 1987.
6. R. Paige. Programming with Invariants. Research Report IBM, No 0, October 1985.

Miscellaneous

1. C. Demetrescu, G.F. Italiano. Dynamic Shortest Paths and Transitive Closure: an Annotated Bibliography (Draft). 2005.
2. Daniel Brixen. Incremental Methods for REA-based Reporting. M.S. thesis, Department of Computer Science, University of Copenhagen, January 2005.
3. Giuseppe F. Italiano. Fully Dynamic Problems on Undirected Graphs. Lecture notes. Chapter 4 of something, 1995.
4. R. Nikhil. An Incremental, Strongly Typed, Database Query Language. 1989.
5. M. Paull, C. Cheng, M. Berman. Incremental Algorithms. 1984.
6. D. Harel. On Line Maintenance of the Connected Components of Dynamic Graphs. 1983.
7. B. MacLennan. Preliminary Investigation of a Calculus of Functional Differences: Fixed Differences. 0.

Dissertations

1. P. Sankowski. Algebraic graph algorithms. PhD Thesis Institute of Informatics, February 2005.
2. Camil Demetrescu. Fully Dynamic Algorithms for Path Problems on Directed Graphs. PhD Thesis University of Rome La Sapienza, 2001.
3. Y.A. Liu. Incremental computation: a semantics-based systematic transformational approach. PhD Thesis Cornell University, 1996.
4. A.M. Berman. Lower and upper bounds for incremental algorithms. PhD Thesis Rutgers University, 1992.
5. Görel Hedin. Incremental Semantic Analysis. PhD Thesis Dept. of Computer Science, Lund University, March 1992.
6. T. Marlowe. Data Flow Analysis and Incremental Iteration. PhD Thesis Rutgers University, October 1989.

Master's thesis

1. S. Even, H. Gazit. Updating Distances in Dynamic Graphs. Master's theses Technion, Haifa, Israel, May 1983.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.