Workshop on Algorithm Engineering

Ca' Dolfin, Venice, Italy, September 11-13, 1997


Conference Program


Thursday September 11, 1997

Registration (9:00 - 9:45)

Welcome address (9:45 - 10:00)

Session I (10:00 - 11:25) Session Chair: G. F. Italiano

Invited Lecture (10:00 - 11:00) Kurt Mehlhorn, MPI Saarbruecken, Shortest paths in secondary memory (joint work with Andreas Crauser and Uli Meyer).

Augment or push? A computational study of bipartite matching and unit capacity maximum flow algorithms, B. V. Cherkassky, A. V. Goldberg, P. Martin, J. C. Setubal and J. Stolfi (11:00 - 11:25)

Coffee break (11:25 - 11:45)

Session II (11:45 - 13:00) Session Chair: A. V. Goldberg

Implementations of dynamic tree collections based on splay trees, T. Radzik (11:45 - 12:10)

Greedy matching algorithms, an experimental study, J. Magun (12:10 - 12:35)

Efficient, adaptable implementations of graph algorithms, D. Kuehl, M. Nissen and K. Weihe (12:35 - 13:00)

Session III (14:45 - 16:20)Session Chair: K. Mehlhorn

State of the art talk (14:45 - 15:30) Andrew V. Goldberg, NEC What to solve: Designing computational data sets

Practical performance of efficient minimum cut algorithms M. Juenger, G. Rinaldi and S. Thienel (15:30 - 15:55)

Experimental analysis of dynamic algorithms for the single source shortest path problem, D. Frigioni, M. Ioffreda, U. Nanni and G. Pasqualone (15:55 - 16:20)

Coffee break (16:20 - 16:40)

Session IV (16:40 - 17:55)Session Chair: B. Moret

A first experimental study of a dynamic transitive closure algorithm, T. Miller and C. Zaroliagis (16:40 - 17:05)

Reactive local search for maximum clique, R. Battiti and M. Protasi (17:05 - 17:30)

A discrete neural algorithm for the maximum clique problem: analysis and circuit implementation, A. Bertoni, P. Campadelli and G. Grossi (17:30 - 17:55)

Business Meeting (18:00 - 19:00)


Friday September 12, 1997

Session V (9:30 - 10:55) Session Chair: G. Ausiello

Invited Lecture (9:30 - 10:30) Franco P. Preparata, Brown University Steps into robust computational geometry.

Early experiences in implementing the buffer tree, D. Hutchinson, A. Maheswari, J. Sack and R. Velicescu (10:30 - 10:5)

Coffee break (10:55 - 11:15)

Session VI (11:15 - 12:55) Session Chair:

The ice rink problem, B. Moret, M. Collins, J. Saia and L. Yu (11:15 - 11:40)

AGD--Library: a library of algorithms for graph drawing, D. Alberts, C. Gutwenger, P. Mutzel and S. Naeher (11:40 - 12:05)

A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem U. Bratuschka, K. Mehlhorn and S. Naeher (12:05 - 12:30)

A case study in algorithm engineering for geometric computing, R. Tamassia, L. Vismara and J. Baker (12:30 - 12:55)

Session VII (14:45 - 16:20) Session Chair: F. P. Preparata

State of the art talk (14:45 - 15:30) The LEDA platform of combinatorial and geometric computing, Stefan Naeher, Univ. Halle

LEONARDO: a software visualization system, P. Crescenzi, C. Demetrescu, I. Finocchi and R. Petreschi (15:30 - 15:55)

Implementing radixsort, A. Andersson and S. Nilsson (15:55 - 16:20)

Coffee break (16:20 - 16:40)

Session VIII (16:40 - 17:55) Session Chair: S. Naeher

The architecture of a software library for string processing, A. Czumaj, P. Ferragina, L. Gasieniec, S. Muthukrishnan and J. Traeff (16:40 - 17:05)

Vertex-to-vertex rarallel radiosity on clusters of PCs, A. Bar-Lev, A. Itzkovitz, A. Raviv and A. Schuster (17:05 - 17:30)

Fast compression state lookup of Internet packet headers, B. Nordgren and M. Sundstrom (17:30 - 17:55)

Social dinner (19.30)


Saturday September 13, 1997

Session IX (9:30 - 11:15)

State of the art talk (9:30 - 10:15)Mike Juenger, Univ. Koeln Implementing combinatorial optimization software in ABACUS

Invited Lecture (10:15 - 11:15) Massimo Bernaschi, IBM Semea A parallel algorithm for the simulation of the Immune Response

Coffee break (11:15 - 11:35)

Session X (11:35 - 13:00) Session Chair: K. Weihe

Computing Groebner bases in the Boolean setting with Applications to Counting, A. Bernasconi, B. Codenotti, V. Crespi and G. Resta (11:35 - 12:00)

Data structure for solving programming problems concerning segments in a sequence, Y. Futamura, C. Shirai, Y. Liu, N. Futamura and K. Kakehi (12:00 - 12:25)

Database learning: a method for empirical algorithm design, M. Goldberg and D. Hollinger (12:25 - 12:50)

Concluding remarks (12:50-13:00)