General

The deadline for the workshop is 15/05/03.

We receive the LEDA please contact me (Liam) to receive a copy.

Here I add a project named my_demo which works with two different files.

The first one is the file my_demo.c which contains the simple example word_count

from the book or from the getting started. The second file is my_demo1.c which contains one

of the implementation of dijkstra algorithm (the one under directory \test\graph)

all the files pass compilation.

The workshop hours:

Prof. Uri Zwick (9610) Wednesday 10:00-12:00

Wednesday 12:00-15:00

Liam Roditty (5398) Tuesday 16:00-19:00

Please try to schedule it with us from advance.

Email list:

http://listserv.tau.ac.il/archives/cs0368-3500-18.html

Please add your email to the email list.

Topics

1. Dynamic reachability in directed graphs
2. Dynamic connectivity in undirected graph
3. Shortest paths
4. Approximate Shortest paths
5. SAT
6. Coloring

Dynamic reachability in directed graphs (Close)

Theoretical papers

An On-Line Edge-Deletion Problem

Yossi Shiloach and Shimon Even

Journal of the ACM (JACM) Volume 28 ,  Issue 1.

Finding Paths and Deleting Edges in Directed Acyclic Graphs.

Giuseppe F. Italiano

Information Processing Letters 28(1): 5

Improved dynamic reachability algorithms for directed graphs.

L. Roditty and U Zwick.

In Proceedings of the 43th Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, 2002.

A faster and simpler fully dynamic transitive closure.

L. Roditty

In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA; 12--14 January 2003

Experimental papers

An Experimental Study of Dynamic Algorithms for Transitive Closure.

D. Frigioni, T. Miller, U. Nanni, C. Zaroliagis

To appear on ACM Journal on Experimental Algorithmics, ACM.

Dynamic connectivity in undirected graph

Theoretical papers

An On-Line Edge-Deletion Problem

Yossi Shiloach and Shimon Even

Journal of the ACM (JACM) Volume 28 ,  Issue 1(1981).

Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications.

Greg N. Frederickson

SIAM J. Comput. 14(4): 781-798 (1985).

Sparsification - a technique for speeding up dynamic graph algorithms.

David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig:

JACM 44(5): 669-696 (1997)

Randomized fully dynamic graph algorithms with polylogarithmic time per operation

Monika Rauch Henzinger, Valerie King

JACM 46(4): 502-516 (1999)

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Jacob Holm , Kristian de Lichtenberg  and Mikkel Thorup

JACM 48(4): 723-760 (2001)

Experimental papers

An empirical study of dynamic graph algorithms

David Alberts, Giuseppe Cattaneo, and Giuseppe. F. Italiano

Journal of Experimental Algorithmics (JEA)}, 2:5, 1997.

Shortest paths

Scaling Algorithms for the Shortest Paths Problem

V. Goldberg

SIAM Journal on Computing, Vol. 24, pages 494-504, May 1995.

Approximate Shortest paths

All Pairs Almost Shortest Paths

Dorit Dor, Shay Halperin, Uri Zwick,
SIAM Journal on Computing 29, 1740-1759 (2000).

All-Pairs Small-Stretch Paths

Edith Cohen, Uri Zwick

Proc. of 8th SODA (1997), 93-102.

Approximate Distance Oracles

Mikkel Thorup, Uri Zwick,
Proc. of 33rd STOC (2001), 183-192.

SAT

Coloring

Conventions

Workshop on Algorithm Engineering and Experiments (ALENEX) ALENEX 2002

Workshop on Algorithm Engineering (WAE) WAE 2002

Journals

ACM Journal on Experimental Algorithms (JEA)

Tools

Leda (A platform for combinatorial and geometric computing)