ALENEX 99 Program

Contributed talks are 20 minutes; invited talks are 60 minutes.

8:15 Greetings and announcements -- McGeoch, Goodrich

8:30 -- 9:50 Combinatorial Algorithms (Chair Johnson)

Efficient implementation of the WARM-UP algorithm for the construction of length-restricted prefix codes. Ruy Luiz Milidi(u'), Artur Alves Pessoa, and Eduardo Sany Laber, PUC-RJ, Rio de Janeiro.
Implementing weighted b-matching algorithms: insights from a computational study. Matthias M(u)ller-Hannemann and Alexander Schwartz, Technische Unviersit(a)t Berlin.
Circular drawings of biconnected graphs. Janet M. Six and Ioannis G. Tollis, University of Texas at Dallas
Heuristics and experimental design for bigraph crossing number minimization. Matthias Stallmann, Franc Brglez, and Debabrata Gosh, N.C. State University.

9:50 --10:20 break

10:20--11:20 Computational Geometry (Chair Tamassia)

A case study on the cost of geometric computing. Stefan Schirra, Max-Planck-Institute.
Binary space partitions in Pl(u)cker Space. David M. Mount and Fan-Tao Pu, University of Maryland.
Practical point-in-polygon tests using CSG representations of polygons. Robert J. Walker and Jack Snoeyink, UCB

11:20 -- 1:00 lunch

1:00 -- 2:00 Invited talk by Kurt Mehlhorn

2:00 -- 2:30 break

2:30 -- 5:30 Papers from the DIMACS Challenge (TBA)

8:15 Greetings and announcements

8:30 --9:40 Software and Applications (Chair Skienna)

(10 minutes for announcements of software libraries and repositories)
Accessing the internal organization of data structures in the JDSL library. Michael T. Goodrich, Mark Handy, Beno(i) Hudson, and Roberto Tamassia, Johns Hopkins University and Brown University.
Object-oriented design of graph oriented data structures. Maurizio Pizzonia and Guiseppe Di Battista, Universit(`a) di Roma.
Design and implementation of Fiduccia-Mattheyses heuristic for VLSI netlist partitioning. Andrew E. Caldwell, Andrew B. Kahng and Igor L. Markov, UCLA.

9:40--10:00 break

10:00--11:20 Applications (Chair Italiano)

Algorithms for restoration planning in a telecommunications network. M. Deng, D. F. Lynch, S. J. Phillips, and J. R. Westbrook, AT&T Labs-Research.
Computing the nxm shortest paths efficiently. Tetsuo Shibuya, IBM Research Division, Tokyo.
Image watermarking for copyright protection. Gregory L. Heileman, Carlos E. Pizano, Lawrence W. Irwin, and Chaouki T. Abdallah, University of New Mexico.
Designing practical efficient algorithms for symmetric multiprocessors. David R. Helman and Joseph J(a)j(a), University of Maryland

11:20 -- 1:00 lunch

1:00 -- 2:00 Invited talk by Jon Bentley

2:00 -- 2:15 break

2:15 -- 3:15 Algorithms for NP-Hard Problems (Chair Battiti)

A self-organizing bin packing heuristic. Janos Csirik, David S. Johnson, Claire Kenyon, Peter W. Shor, and Richard Weber, University of Szeged, AT&T Labs, Universit(e) Paris-Sud, and University of Cambridge.
Finding the right cutting planes for the TSP. Matthew S. Levine, MIT/AT&T Labs
Obstacle-avoiding Euclidean Steiner trees in the plane: an exact algorithm. Martin Zachariasen and Pawel Winter, University of Copenhagen.

3:15 -- 3:45 break

3:45 -- 4:45 3x Data Structures (Chair Karger)

Adaptive algorithms for cache-efficient trie search. Anurag Acharya, Huican Zhu, and Kai Shen, University of California, Santa Barbara.
Fast priority queues for cached memory. Peter Sanders, Max-Planck Institut
Efficient bulk operations on dynamic R-trees. Lars Arge, Klaus H. Hinrichs, Jan Vahrenhold, and Jeffry S. Vitter, Duke University and Westf(a)lische Whilhelms-Universit(a)t.

4:45 -- 5:00 Meeting on the future of ALEX and ALENEX