SWAT'2000 Program

Tourist:
Bergen
Norway
Weather

                  Program of SWAT'2000 
     7th Biennial Scandinavian Workshop on Algorithm Theory
        July 5-7, 2000 - Hotel Terminus, Bergen, Norway

May 22: Last day to reserve hotel room and avoid late fee. 
        Register at http://www.ii.uib.no/swat2000/registration

** Tuesday July 4, 18:00 Welcoming reception ***************

** Wednesday July 5 ****************************************

** Session 1: Data structures 

8:40 A new trade-off for deterministic dictionaries
Rasmus Pagh

9:00 Improved upper bounds for pairing heaps
John Iacono

9:20 Maintaining center and median in dynamic trees
Stephen Alstrup, Jacob Holm, Mikkel Thorup

9:40 Dynamic Planar Convex Hull with Optimal Query Time
and $O(\log n\cdot\log\log n)$ Update Time
Gerth Brodal, Rico Jacob 

10:00-10:20 Coffee break

** Session 2: Invited talk 
10:20 Dynamic Graph Algorithms with Applications
Mikkel Thorup

** Session 3: Dynamic partitions 

11:20 A dynamic algorithm for maintaining graph partitions
L.G. Aleksandrov, H. N. Djidjev

11:40 Data structures for maintaining set partitions
Michael Bender, Saurabh Sethia, Steven Skiena 

12:00-14:00 Lunch

** Session 4: Graph algorithms 

14:00 Fixed parameter algorithms for Planar Dominating Set and related problems
Jochen Alber, Hans Bodlaender, Henning Fernau, Rolf Niedermeier

14:20 Embeddings for k-connected graphs of pathwidth k
Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde

14:40 On graph powers for leaf-labeled trees
Naomi Nishimura, Prabhakar Ragde, Dimitrios Thilikos 

15:00 Recognizing weakly triangulated graphs by edge separability
Anne Berry, Jean-Paul Bordat, Pinar Heggernes

15:20-15:40 Coffee break

** Session 5: Online algorithms 

15:40 Caching for web searching
Bala Kalyanasundaram, John Noga, Kirk Pruhs, Gerhard Woeginger

16:00 On-line scheduling with precedence constraints
Yossi Azar, Leah Epstein

16:20 Scheduling jobs before shut-down
Vincenzo Liberatore

16:40 Resource augmentation in load balancing
Yossi Azar, Leah Epstein, Rob van Stee

17:00 Fair versus unrestricted bin packing
Yossi Azar, Joan Boyar, Lene Favrholdt, Kim S. Larsen, Morten Nielsen

** Business meeting (17:30)

** Thursday July 6 ***********************************************

** Session 6: Approximation algorithms 

8:40 A d/2 approximation for maximum weight independent set in d-claw free graphs
Piotr Berman

9:00 Approximation algorithms for the label-cover(MAX) and red-blue set cover problems
David Peleg

9:20 Approximation algorithms for maximum linear arrangement
Refael Hassin, Shlomi Rubinstein

9:40 Approximation algorithms for clustering to minimize the sum of diameters
Srinivas Doddi, Madhav Marathe, S.S. Ravi, David Taylor, Peter Widmayer

10:00-10:20 Coffee break

** Session 7: Invited talk 
10:20 Coping with NP-hardness of the Graph Bandwidth Problem
Uriel Feige

** Session 8: Matchings 

11:20 Robust matchings and maximum clustering
Refael Hassin, Shlomi Rubinstein

11:40 The hospitals/resident problem with ties
Robert Irving, David Manlove, Sandy Scott

12:00-14:00 Lunch

** Session 9: Network design 

14:00 Incremental maintenance of the 5-edge-connectivity classes of a graph
Yefim Dinitz, Ronit Teplixke

14:20 On the minimum augmentation of an l-connected graph to a k-connected graph
Toshimasa Ishii, Hiroshi Nagamochi

14:40 Locating sources to meet flow demands in undirected networks
Kouji Arata, Satoru Iwata, Kazuhisa Makino, Satoru Fujishige

15:00 Improved greedy algorithms for constructing sparse geometric spanners
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan

15:20-15:40 Coffee break

** Session 10: Computational Geometry 

15:40 Computing the penetration depth of two convex polytopes in 3D
Pankaj Agarwal, Leonidas Guibas, Sariel Har-Peled, Alexander Rabinovitch, Mich Sharir

16:00 Compact Voronoi diagrams for moving convex polygons
Leonidas Guibas, Jack Snoeyink, Li Zhang

16:20 Efficient expected-case algorithms for planar point location
Sunil Arya, Siu-Wing Cheng, David Mount, Hariharan Ramesh

16:40 A new competitive strategy for reaching the kernel of an unknown polygon
Leonidas Palios

** Banquet (20:00)

** Friday July 7 ************************************************

** Session 11: Strings and algorithm engineering 

8:40 The Enhanced Double Digest Problem for DNA Physical Mapping
Ming-Yang Kao, Jared Samet, Wing-Kin Sung 

9:00 Generalization of a suffix tree for RNA structural pattern matching
Tetsuo Shibuya 

9:20 Efficient computation of all longest common subsequences
Claus Rick

9:40 A blocked all-pairs shortest-paths algorithm
Gayathri Venkatarman, Sartaj Sahni, Srabani Mukhopadhyaya

10:00-10:20 Coffee break

** Session 12: Invited talk 
10:20 Towards Complete Genome Data Mining in Computational Biology
Esko Ukkonen

** Session 13: I/O 

11:20 On external memory MST, SSSP and multi-way planar graph separation
Large Arge, Gerth Brodal, Laura Toma

11:40 I/O-space trade-offs
Large Arge, Jakob Pagter 

12:00-14:00 Lunch

** Session 14: Optimization 

14:00 Optimal flow aggregation
Subhash Suri, Tuomas Sandholm, Priyank Warkhede

14:20 On the complexities of the optimal rounding problems of sequences and matrices
Tetsuo Asano, Tomomi Matsui, Takeshi Tokuyama

14:40 On the complexity of the sub-permutation problem
Shlmo Ahal, Yuri Rabinovich

15:00 Parallel attribute-efficient learning of monotone Boolean functions
Peter Damaschke 

15:20-15:40 Coffee break

** Session 15: Distributed computing and fault-tolerance 

15:40 Max- and min-neighborhood monopolies
Kazuhisa Makino, Masafumi Yamashita, Tiko Kameda

16:00 Optimal adaptive fault diagnosis of hypercubes
Andreas Bjorklund

16:20 Fibonacci correction networks
Grzegorz Stachowiak 

16:40 Least adaptive optimal search with unreliable tests
Ferdinando Cicalese, Daniele Mundici, Ugo Vaccaro

*** Saturday July 8, 8:30-20:00 Excursion ****************************