![]() ![]() ![]() accomodation, and travel ![]() ![]() submissions ![]() ![]() papers ![]() |
University of Bergen
:
Fac. Math and Nat. Sci.
:
Dep. of Informatics
:
Swat'2000
|
![]() ![]() Informatics |
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 **************************** |
![]() |
![]() ![]() This page is maintained by Fredrik.Manne@ii.uib.no |