Publications

Research topics		Copyright notice
Dynamic graph algorithms Data streams Data structures Approximation algorithms Software visualization Graph drawing Programming		The documents available from this site are provided as a means to ensure timely dissemination of  technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will 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 (Springer-Verlag for works appeared in the LNCS series, ACM-SIAM, IEEE, etc.). Permission to make digital or hard copies of part or all of these works for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage. The electronic version of some of the works available from this site may differ from the definitive published version. Copyright of works submitted for publication may be transferred without further notice and this version may no longer be accessible.

Dynamic graph algorithms

C. Demetrescu and G.F. Italiano Dynamic shortest paths and transitive closure: Algorithmic techniques and data structures To appear in Journal of Discrete Algorithms (JDA), 2006. [download pdf, 312 KB] [abstract] [bibtex]

C. Demetrescu and G.F. Italiano Fully Dynamic All Pairs Shortest Paths with Real Edge Weights Journal of Computer and System Sciences (JCSS), 72(5), pp. 813-837, 2006. Special Issue devoted to selected papers from the 42nd Annual IEEE Symposium on Foundations of Computer Science. [abstract] [bibtex] A preliminary version appears in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'01), Las Vegas, Nevada. October 14-17, 2001. Also Technical Report ALCOM-FT, ALCOMFT-TR-01-150, May 2001 [download ps.gz, 112 KB] [download preliminary PowerPoint presentation, 516 KB, 30 slides] [abstract].

C. Demetrescu and G. F. Italiano Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms To appear in ACM Transactions on Algorithms (TALG), 2005. Special Issue devoted to the best papers selected from the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04). [download pdf, 272 KB] [abstract] [bibtex] A preliminary version (with S.Emiliozzi) appears in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04), New Orleans, LA. January 2004.

C. Demetrescu and G.F. Italiano Trade-Offs for Fully Dynamic Reachability: Breaking Through the O(n2) Barrier Journal of the Association for Computing Machinery (JACM), 52(2), pp. 147-156, 2005. [download pdf, 148 KB] [abstract] [bibtex] Some of the results of this paper appeared in: Fully Dynamic Transitive Closure: Breaking Through the O(n2) Barrier. Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS'00), Redondo Beach, Los Angeles, CA. November 12-14, 2000 [download ps.gz, 64 KB] [download PowerPoint presentation, 274 KB, 19 slides] [download slides, ps.gz, 39 KB, 19 slides] [abstract].

C. Demetrescu, I. Finocchi, and G.F. Italiano Dynamic Trees Handbook on Data Structures and Applications, Chapter 35. Dinesh Mehta and Sartaj Sahni (eds.), CRC Press Series, in Computer and Information Science, January 2005. [abstract] [bibtex]

C. Demetrescu, I. Finocchi, and G.F. Italiano Dynamic Graphs Handbook on Data Structures and Applications, Chapter 36. Dinesh Mehta and Sartaj Sahni (eds.), CRC Press Series, in Computer and Information Science, January 2005. [abstract] [bibtex]

C. Demetrescu and G.F. Italiano A New Approach to Dynamic All Pairs Shortest Paths Journal of the Association for Computing Machinery (JACM), 51(6), pp. 968-992, November 2004 [dowload pdf, 280 KB] [abstract] [bibtex] A preliminary version of this paper appears in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC'03), San Diego, California, June 2003.

C. Demetrescu, I. Finocchi, and G.F. Italiano Dynamic Graph Algorithms Handbook of Graph Theory, chapter 10.2, J. Yellen e J.L. Gross eds., CRC Press Series, in Discrete Mathematics and Its Applications, ISBN 1-58488-090-2, pp. 985-1014, December 2003 [download pdf, 320 KB] [bibtex]

C. Demetrescu and G.F. Italiano Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths Proceedings of the 29-th International Colloquium on Automata, Languages, and Programming (ICALP'02), Málaga, Spain, July 2002.

C. Demetrescu Fully Dynamic Algorithms for Path Problems on Directed Graphs Ph.D. Dissertation, Report XIII-01-1, Department of Computer and Systems Science, University of Rome "La Sapienza", April 2001 [download ps.gz, 432 KB] [abstract] [acknowledgements]. Co-winner or the 2002 Italian Chapter EATCS Award for the best Ph.D. thesis in theoretical computer science

C. Demetrescu, D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study Proceedings of the 4-th Workshop on Algorithm Engineering (WAE'00), Saarbruecken, Germany. September 5-8, 2000 [download ps.gz, 144 KB] [download PowerPoint presentation, 108 KB, 18 slides] [abstract].

Data streams

C. Demetrescu, I. Finocchi, and A. Ribichini Trading off space for passes in graph streaming problems Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06), Miami, FL, 2006. [abstract] [download pdf, 348 KB] [download PowerPoint presentation, 1.3 MB, 22 slides]

Data structures

C. Demetrescu and M. Thorup Oracles for Distances Avoiding a Link-failure Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), San Francisco, CA. January 6-8, 2002. Full version: Oracles for Distances Avoiding a Node or Link Failure, also with Rezaul Alam Chaudhury and Vijaya Ramachandran [download pdf, 180 KB] [download PowerPoint presentation, 2.6 MB, 27 slides].

Approximation algorithms

C. Demetrescu and I. Finocchi Combinatorial Algorithms for Feedback Problems in Directed Graphs Information Processing Letters 86 (IPL), pp. 129-136, 2003 [download pdf, 216 KB] [abstract]

Software visualization and development systems

V.Bonifaci, C. Demetrescu, I. Finocchi, G.F. Italiano and L.Laura Visual Editing of Animated Algorithms: the Leonardo Web Builder Proceedings of the 8th International Working Conference on Advanced Visual Interfaces (AVI'06), 2006. [abstract] [bibtex]

V.Bonifaci, C. Demetrescu, I. Finocchi, G.F. Italiano and L.Laura Portraying algorithms with Leonardo Web Proceedings of the WISE’05 International Workshop on Web-based Learning, New York City, USA, Nov 20, 2005.

C. Demetrescu and I. Finocchi A Portable Virtual Machine for Program Debugging and Directing Proceedings of the 19th ACM Symposium on Applied Computing (SAC'04) - Software Engineering Track, pp. 1524-1530.

C. Demetrescu, I. Finocchi, and J. T. Stasko Specifying Algorithm Visualizations: Interesting Events or State Mapping? In Stephan Diehl (Ed.): Software Visualization, International Seminar Dagstuhl Castle, Germany, May 20-25, 2001, Revised Lectures, LNCS 2269, Springer Verlag, 2002. Also Technical Report ALCOM-FT, ALCOMFT-TR-01-177, May 2001 [download pdf, 275 KB]

B.A. Colombo, C. Demetrescu, I. Finocchi, and L. Laura A Java-based System for Building Animated Presentations over the Web Science of Computer Programming (SCP), special issue on "Practice and Experience with Java in Education", Elsevier. An extended abstract appears in the Proceedings of the AICCSA'03 Workshop on Practice and Experience with Java Programming in Education, Tunis, July 2003 [download pdf, 160 KB] [abstract]

C. Demetrescu, I. Finocchi, and G. Liotta Visualizing Algorithms over the Web with the Publication-Driven Approach Proceedings of the 4-th Workshop on Algorithm Engineering (WAE'00), Saarbruecken, Germany. September 5-8, 2000 [download ps.gz, 156 KB] [abstract]

C. Demetrescu, E. Di Giacomo, I. Finocchi, and G. Liotta Visualizing Geometric Algorithms with WAVE: System Demonstration Proceedings of the 10th Annual Fall Workshop on Computational Geometry (CG'00), University at Stony Brook, October 27-28, 2000 [download ps.gz, 48 KB] [download pdf, 148 KB]

P. Crescenzi, C. Demetrescu, I. Finocchi, and R. Petreschi Reversible Execution and Visualization of Programs with Leonardo Journal of Visual Languages and Computing (JVLC), 11(2), pp. 125-150, Academic Press, April 2000 [download ps.gz, 465 KB] A preliminary version appears in Proceedings of the 1st Workshop on Algorithm Engineering (WAE'97), G.F. Italiano and S. Orlando Editors, pp. 146-155, Venice, Italy, September 1997 [download ps.gz, 648 KB].

C. Demetrescu and I. Finocchi Smooth Animation of Algorithms in a Declarative Framework Journal of Visual Languages and Computing (JVLC), 12(3), Special Issue devoted to selected papers from the 15th IEEE Symposium on Visual Languages, Academic Press, 2001 [download ps.gz, 448 KB] A preliminary version appears in Proceedings of the 15th IEEE Symposium on Visual Languages (VL'99), IEEE Computer Society Press, pp. 280-287, Tokyo, Japan, September 1999 [download ps.gz, 154 KB] [download PowerPoint presentation, 104 KB, 32 slides] [abstract].

C. Demetrescu and I. Finocchi A Technique for Generating Graphical Abstractions of Program Data Structures Proceedings of the 3rd International Conference on Visual Information Systems (Visual'99), LNCS 1614, pp. 785-792, Amsterdam, The Netherlands, June 1999 [download ps.gz, 99 KB] [abstract].

C. Demetrescu and I. Finocchi A General-purpose Logic-based Visualization Framework Proceedings of the 7th International Conference in Central Europe on Computer Graphics, Visualization and Interactive Digital Media (WSCG'99), pp. 55-62, Plzen, Czech Republic, February 1999 [download ps.gz, 213 KB] [abstract].

Algorithm engineering

C. Demetrescu and G.F. Italiano Engineering Shortest Path Algorithms Proceedings of the 3rd International Workshop on Experimental and Efficient Algorithms (WEA'04), Angra dos Reis, Brazil, May 25-28, 2004 [download pdf, 128 KB] [abstract].

C. Demetrescu, I. Finocchi, and G.F. Italiano Engineering and visualizing algorithms Proceedings of the 11th International Symposium on Graph Drawing (GD'03), Perugia, Italia, settembre 2003, LNCS 2912, pp. 519--523.

C. Demetrescu, I. Finocchi, and G.F. Italiano Algorithm Engineering In Current Trends in Theoretical Computer Science: the Challenge of the New Century (vol.1: Algorithms and Complexity), G.Paun, G.Rozemberg, A.Salomaa eds., ISBN 981-238-966-0, World Scientific Publishing, 2004. A previous version of the paper appeared in The Algorithmics Column (J.Diaz), Bulletin of the EATCS 79, pp. 48-63, February 2003 [download pdf, 168 KB] [abstract]

C. Demetrescu, I. Finocchi, G.F. Italiano, and S. Naeher Visualization in Algorithm Engineering: Tools and Techniques In R. Fleischer, B. Moret, E. Meineche Schmidt (Eds.): Experimental Algorithmics, From Algorithm Design to Robust and Efficient Software, LNCS 2547, Springer Verlag, 2002. Also Technical Report ALCOM-FT, ALCOMFT-TR-01-149, May 2001 [download ps.gz, 592 KB].

C. Demetrescu and G.F. Italiano What Do We Learn from Experimental Algorithmics? Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS'00), Bratislava, Slovak Republic, August 28 - September 1, 2000 [download ps.gz, 224 KB] [download Powerpoint presentation, zipped, 1.1 MB, 37 slides] [download html slides, tar.gz, 700 KB, 35 slides] [abstract].

Graph drawing

C. Demetrescu and I. Finocchi Breaking Cycles for Minimizing Crossings ACM Journal on Experimental Algorithmics (JEA), 6(1). Special Issue devoted to selected papers from the 2nd International Workshop on Algorithms Engineering and Experiments. Also in Technical Report ALCOM-FT, ALCOMFT-TR-01-148, May 2001 [download ps.gz, 740 KB] Extended abstract: C. Demetrescu and I. Finocchi: Break the 'Right' Cycles and Get the 'Best' Drawing, Proceedings of the 2nd International Workshop on Algorithms Engineering and Experiments (ALENEX'00), pp. 171-182, San Francisco, CA, January 2000 [download ps.gz, 252 KB] [download PowerPoint presentation, 192 KB, 26 slides].

C. Demetrescu, G. Di Battista, I. Finocchi, G. Liotta, M. Patrignani, and M. Pizzonia Infinite Trees and the Future Proceedings of the 7-th International Symposium on Graph Drawing (GD'99), LNCS 1731, pp. 379-391, Prague, September 1999 [download ps.gz, 128 KB] [abstract].

Programming, algorithms and data structures
	C. Demetrescu, I. Finocchi, and Giuseppe F. Italiano Algoritmi e Strutture Dati ISBN 88-386-6161-8. McGraw-Hill, 2004 (in italian ) [website]		D. Calvanese, G. De Giacomo, C. Demetrescu, L. Iocchi, and D. Nardi Lezioni di Fondamenti di Informatica December 2002 (in italian ), Edizioni Esculapio.
C. Demetrescu and F. Quaglia Programming in the UNIX environment September 1999 (in italian ) [download pdf].		C. Demetrescu and I. Finocchi The Leonardo User Manual [online html] [download html, sit.bin, 674 KB] [download html, tar.gz, 620 KB].

Some slides

C. Demetrescu and I. Finocchi Fun with Leonardo lecture, Dagstuhl Seminar 01211 on Software Visualization, May 2001 [download PowerPoint presentation, 252 KB, 17 slides].

C. Demetrescu Dynamic Algorithms lecture, Lezione Informatica Teorica, May 2001(in italian ) [download PowerPoint presentation, 136 KB, 15 slides].

C. Demetrescu and M. Thorup Distance Sensitivity Oracles lecture, Workshop 2nd year, MURST project "Algorithms for Large Data Sets: Science and Engineering", February 2001 [download PowerPoint presentation, 116 KB, 11 slides] [download slides ps.gz, 212 KB, 11 slides].

C. Demetrescu Algorithm Engineering: Difficulties and Success Stories lecture, Seminario Interdipartimentale di Algoritmica, October 2000 [download PowerPoint presentation, 1199 KB, 27 slides].

C. Demetrescu and G.F. Italiano Dynamic Matrices for Fully Dynamic Transitive Closure lecture, Oberwolfach Meeting 32/2000 on Efficient Algorithms, August 2000 [download PowerPoint presentation, 276 KB, 28 slides].

C. Demetrescu and G.F. Italiano Fully Dynamic Transitive Closure: Breaking Through the O(n2) Barrier lecture, Oberwolfach Meeting 32/2000 on Efficient Algorithms, August 2000 [download PowerPoint presentation, 116 KB, 15 slides].

C. Demetrescu Algorithm Animation over the World Wide Web lecture, Workshop 1st year, MURST project "Algorithms for Large Data Sets: Science and Engineering", February 2000 [download PowerPoint presentation, 72 KB, 10 slides].

Last updated: May 22, 2006. [an error occurred while processing this directive]