Thursday, December 16, 1999
0815-0900 : Registration
0900-1000 : Invited Talk 1
1015-1115 : Session 1(a) - Data Structure I
General Splay : A Basic Theory and Calculus
G.F.Georgakapoulos and D.J.McClurkin
Static Dictionaries Supporting Rank
Venkatesh Raman and S.Srinivasa Rao
1015-1115 : Session 1(b) - Parallel & Distributed Computing I
Multiple Spin-Block Decisions
Peter Damaschke
Asynchronous Random Polling Dynamic Load Balancing
Peter Sanders
1115-1130 : Tea
1130-1230 : Session 2(a) - Approximate Algorithm I
Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability
Daya Ram Gaur and Ramesh Krishnamurti
Hardness of Approximating Independent Domination in Circle Graphs
Mirela Damian-Irodache and Sriram V. Pemmaraju
Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs
Mirela Damian-Iordache and Sriram V. Pemmaraju
1130-1230 : Session 2(b) - Computational Intelligence
Ordered Binary Decision Diagrams as Knowledge-Bases
Takashi Horiyama and Toshihide Ibaraki
Hard Tasks For Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro and Peter Widmayer
1230-0200 : Lunch
0200-0300 : Session 3(a) - Online Algorithm
On On-line Load Balancing
Kar-Keung To and Wai-Ha Wong
Online Routing in Triangulations
Prosenjit Bose and Pat Morin
0200-0300 : Session 3(b) - Complexity Theory I
The Query Complexity of Program Checking by Constant-Depth Circuits
V.Arvind, K.V.Subrahmanyam and N.V.Vinodchandran
Tree-Like Resolution is Exponentially Slower Than DAG-Like Resolution for the Pigeonhole Principle
Kazuo Iwama and Shuichi Miyazaki
0300-0330 : Tea
0330-0430 : Session 4(a) - Approximate Algorithm II
Efficient Approximation Algorithms for Multi-Label Map Labeling
Binhai Zhu and C.K.Poon
Approximation Algorithms in Batch Processing
Xiaotie Deng, Chung Keung Poon and Yuzhong Zhang
0330-0430 : Session 4(b) - Graph Algorithm I
LexBFS-ordering in Asteroidal Triple-free Graphs
Jou-Ming Chang, Chin-Wen Ho and Ming-Tat Ko
Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs
F.R.Hsu, Yaw-Ling Lin and Yin-Te Tsai
Friday, December 17, 1999
0900-1000 : Invited Talk 2
1015-1115 : Session 5(a) - Computational Geometry I
How Many People Can Hide in a Terrain?
Stephan Eidenbenz
Carrying Umbrellas : An Online Relocation Problem on Graphs
Jae-Ha Lee, Chong-Dae Park and Kyung-Yong Chwa
1015-1115 : Session 5(b) - Parallel & Distributed Computing II
Survivable Networks with Bounded Delay : The Edge Failure Case
Serafino Cicerone, Gabriele Di Stefano and Dagmar Handke
Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks
J.L.Bordim, J.Cui, T.Hayashi, K.Nakano and S.Olariu
1115-1130 : Tea
1130-1230 : Session 6(a) - Data Structure II
Constructing the Suffix Tree of a Tree with a Large Alphabet
Tetsuo Shibuya
An O(1) Time Algorithm for Generating Multiset Permutations
Tadao Takaoka
1130-1230 : Session 6(b) - Complexity Theory II
Upper Bounds for MaxSat : Further Improved
Nikhil Bansal and Venkatesh Raman
A Linear Time Algorithm for Recognizing Regular Boolean Functions
Kazuhisa Makino
1230-0200 : Lunch
0200-0300 : Session 7(a) - Computational Geometry II
Station Layouts in the Presence of Location Constraints
Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc and David Peleg
Reverse Center Location Problem
Jianzhong Zhang, Xiaoguang Yang and Mao-cheng Cai
0200-0300 : Session 7(b) - Algorithms in Practice
Performance Comparison of linear sieve and cubic sieve algorithms for discrete logarithms over prime fields.
Abhijit Das and C.E.Veni Madhavan
External Memory Algorithms for Outerplanar Graphs
Anil Maheshwari and Norbert Zeh
0300-0330 : Tea
0330-0430 : Session 8(a) - Approximate Algorithm III
A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree.
Tetsuo Asano, Naoki Katoh and Kazuhiro Kawashima
Approximation algorithms for channel assignment with constraints
Jeannette Janssen and Lata Narayanan
0330-0430 : Session 8(b) - Graph Algorithm II
Algorithms for finding noncrossing Steiner forests in plane graphs
Yoshiyuki Kusakari, Daisuke Masubuchi and Takao Nishizeki
A Linear Algorithm for Finding Total Colorings of Planar Partial k-Trees
Shuji Isobe, Xiao Zhou and Takao Nishizeki
Saturday, December 18, 1999
0900-1000 : Invited Talk 3
1015-1115 : Session 9(a) - Approximate Algorithm IV
Approximating Multicast Congestion
Santosh Vempala and Berthold Voecking
Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts
Liang Zhao, Hiroshi Nagamochi and Toshihide Ibaraki
1015-1115 : Session 9(b) - Parallel & Distributed Computing III
Online Scheduling of Parallel Communications with Individual Deadlines
Jae-Ha Lee and Kyung-Yong Chwa
A Faster Algorithm for Finding Disjoint Paths in Grids
Wun-Tat Chan, Francis Y.L.Chin and Hing-Fung Ting
1115-1130 : Tea
1130-1230 : Session 10(a) - Computational Geometry III
Output-Sensitive Algorithms for Uniform Partitions of Points
Pankaj K. Agarwal, Binay K. Bhattacharya and Sandeep Sen
Convexifying Monotone Polygons
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins and Michael A. Soss
1130-1230 : Session 10(b) - Graph Algorithm III
Bisecting Two Subsets in 3-Connected Graphs
Hiroshi Nagamochi, Tibor Jordan, Yoshitaka Nakao and Toshihide Ibaraki
Generalized Maximum Independent Sets for Trees
B.K.Bhattacharya and M.E. Houle