Invited Talk |
The Engineering of Some Bipartite Matching Programs / Kurt Mehlhorn |
Data Structure I / Session 1(a): |
General Splay: A Basic Theory and Calculus / G.F. Georgakopoulos ; D.J. McClurkin |
Static Dictionaries Supporting Rank / Venkatesh Raman ; S. Srinivasa Rao |
Parallel & Distributed Computing I / Session 1(b): |
Multiple Spin-Block Decisions / Peter Damaschke |
Asynchronous Random Polling Dynamic Load Balancing / Peter Sanders |
Approximate Algorithm I / Session 2(a): |
Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colarability / Daya Ram Gaur ; Ramesh Krishnamurti |
Hardness of Approximating Independent Domination in Circle Graphs / Mirela Damian-Iordache ; Sriram V. Pemmaraju |
Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs |
Computational Intelligence / Session 2(b): |
Ordered Binary Decision Diagrams as Knowledge-Bases / Takashi Horiyama ; 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 ; Peter Widmayer |
Online Algorithm / Session 3(a): |
On-Line Load Balancing of Temporary Tasks Revisited / Kar-Keung To ; Wai-Ha Wong |
Online Routing in Triangulations / Prosenjit Bose ; Pat Morin |
Complexity Theory I / Session 3(b): |
The Query Complexity of Program Checking by Constant-Depth Circuits / V. Arvind ; K.V. Subrahmanyam ; N.V. Vinodchandran |
Tree-Like Resolution Is Superpolynomially Slower Than DAG-LikeResolution for the Pigeonhole Principle / Kazuo Iwama ; Shuichi Miyazaki |
Approximate Algorithm II / Session 4(a): |
Efficient Approximation Algorithms for Multi-label Map Labeling / Binhai Zhu ; C.K. Poon |
Approximation Algorithms in Batch Processing / Xiaotie Deng ; Chung Keung Poon ; Yuzhong Zhang |
Graph Algorithm I / Session 4(b): |
LexBFS-Ordering in Asteroidal Triple-Free Graphs / Jou-Ming Chang ; Chin-Wen Ho ; Ming-Tat Ko |
Parallel Algorithms for Shortest Paths and Related Problems on Trapezoid Graphs / F.R. Hsu ; Yaw-Ling Lin ; Yin-Te Tsai |
Approximation Algorithms for Some Clustering and Classification Problems / Eva Tardos |
Computational Geometry I / Session 5(a): |
How Many People Can Hide in a Terrain? / Stephan Eidenbenz |
Carrying Umbrellas: An Online Relocation Problem on Graphs / Jae-Ha Lee ; Chong-Dae Park ; Kyung-Yong Chwa |
Parallel & Distributed Computing II / Session 5(b): |
Survivable Networks with Bounded Delay: The Edge Failure Case / Serafino Cicerone ; Gabriele Di Stefano ; Dagmar Handke |
Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks / J.L. Bordim ; J. Cui ; T. Hayashi ; K. Nakano ; S. Olariu |
Data Structure II / Session 6(a): |
Constructing the Suffix Tree of a Tree with a Large Alphabet / Tetsuo Shibuya |
An O(1) Time Algorithm for Generating Multiset Permutations / Tadao Takaoka |
Complexity Theory II / Session 6(b): |
Upper Bounds for MaxSat: Further Improved / Nikhil Bansal |
A Linear Time Algorithm for Recognizing Regular Boolean Functions / Kazuhisa Makino |
Computational Geometry II / Session 7(a): |
Station Layouts in the Presence of Location Constraints / Christos Kaklamanis ; Lefteris M. Kirousis ; Evangelos Kranakis ; Danny Krizanc ; David Peleg |
Reverse Center Location Problem / Jianzhong Zhang ; Xiaoguang Yang ; Mao-cheng Cai |
Algorithms in Practice / Session 7(b): |
Performance Comparison of Linear Sieve and Cubic Sieve Algorithms forDiscrete Logarithms over Prime Fields / Abhijit Das ; C.E. Veni Madhavan |
External Memory Algorithms for Outerplanar Graphs / Anil Maheshwari ; Norbert Zeh |
Approximate Algorithm III / Session 8(a): |
A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree / Tetsuo Asano ; Naoki Katoh ; Kazuhiro Kawashima |
Approximation Algorithms for Channel Assignment with Constraints / Jeannette Janssen ; Lata Narayanan |
Graph Algorithm II / Session 8(b): |
Algorithms for Finding Noncrossing Steiner Forests in Plane Graphs / Yoshiyuki Kusakari ; Daisuke Masubuchi ; Takao Nishizeki |
A Linear Algorithm for Finding Total Colorings of Partial k-Trees / Shuji Isobe ; Xiao Zhou |
Topology-Oriented Approach to Robust Geometric Computation / Kokichi Sugihara |
Approximate Algorithm IV / Session 9(a): |
Approximating Multicast Congestion / Santosh Vempala ; Berthold Vöcking |
Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts / Liang Zhao ; Hiroshi Nagamochi |
Parallel & Distributed Computing III / Session 9(b): |
Online Scheduling of Parallel Communications with Individual Deadlines |
A Faster Algorithm for Finding Disjoint Paths in Grids / Wun-Tat Chan ; Francis Y.L. Chin ; Hing-Fung Ting |
Computational Geometry III / Session 10(a): |
Output-Sensitive Algorithms for Uniform Partitions of Points / Pankaj K. Agarwal ; Binay K. Bhattacharya ; Sandeep Sen |
Convexifying Monotone Polygons / Therese C. Biedl ; Erik D. Demaine ; Sylvain Lazard ; Steven M. Robbins ; Michael A. Soss |
Graph Algorithm III / Session 10(b): |
Bisecting Two Subsets in 3-Connected Graphs / Tibor Jordán ; Yoshitaka Nakao |
Generalized Maximum Independent Sets for Trees in Subquadratic Time / B.K. Bhattacharya ; M.E. Houle |
Author Index |
Invited Talk |
The Engineering of Some Bipartite Matching Programs / Kurt Mehlhorn |
Data Structure I / Session 1(a): |