| Invited Presentation |
| The Discrepancy Method / Bernard Chazelle |
| Implementing Algorithms and Data Structures: An Educational and Research Perspective / Roberto Tamassia |
| Geometry I |
| Facility Location on Terrains / Evanthia Papadopoulou ; Boris Aronov ; Marc van Kreveld ; René van Oostrum ; Kasturirangan Varadarajan |
| Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles / Joonsoo Choi ; Chan-Su Shin ; Sung Kwon Kim |
| Complexity I |
| Maximizing Agreement with a Classification by Bounded or Unbounded Number of Associated Words / Hiroki Arimura ; Shinichi Shimozono |
| Disjunctions of Horn Theories and Their Cores / Thomas Eiter ; Toshihide Ibaraki ; Kazuhisa Makino |
| Checking Programs Discreetly: Demonstrating Result-Correctness Efficiently While Concealing It / Giovanni Di Crescenzo ; Kouichi Sakurai ; Moti Yung |
| Graph Drawing |
| Two-Layer Planarization in Graph Drawing / Petra Mutzel ; René Weiskircher |
| Computing Orthogonal Drawings in a Variable Embedding Setting / Walter Didimo ; Giuseppe Liotta |
| Dynamic Grid Embedding with Few Bends and Changes / Ulrik Brandes ; Dorothea Wagner |
| On-Line Algorithm and Scheduling |
| Two New Families of List Update Algorithms / Frank Schulz |
| An Optimal Algorithm for On-Line Palletizing at Delivery Industry / J. Rethmann ; E. Wanke |
| On-Line Scheduling of Parallel Jobs with Runtime Restrictions / Stefan Bischof ; Ernst W. Mayr |
| CAD/CAM and Graphics |
| Testing the Quality of Manufactured Disks and Cylinders / Prosenjit Bose ; Pat Morin |
| Casting with Skewed Ejection Direction / Hee-Kap Ahn ; Siu-Wing Cheng ; Otfried Cheong |
| Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image / Tetsuo Asano ; Hiro Ito ; Souichi Kimura ; Shigeaki Shimazu |
| Graph Algorithm I |
| k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph / Toshimasa Ishii ; Hiroshi Nagamochi |
| Polyhedral Structure of Submodular and Posi-modular Systems |
| Maximizing the Number of Connections in Optical Tree Networks / Thomas Erlebach ; Klaus Jansen |
| Best Paper Presentation |
| Selecting the k Largest Elements with Parity Tests / Tak Wah Lam ; Hing Fung Ting |
| Randomized Algorithm |
| Randomized K-Dimensional Binary Search Trees / Amalia Duch ; Vladimir Estivill-Castro ; Conrado MartÃnez |
| Randomized 0(log log n)-Round Leader Election Protocols in Packet Radio Networks / Koji Nakano ; Stephan Olariu |
| Random Regular Graphs with Edge Faults: Expansion through Cores / Andreas Goerdt |
| Complexity II |
| A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem / Takashi Mihara ; Shao Chin Sung |
| Generalized Graph Colorability and Compressibility of Boolean Formulae / Richard Nock ; Pascal Jappy ; Jean Sallantin |
| On the Complexity of Free Monoid Morphisms / Klaus-Jörn Lange ; Pierre McKenzie |
| Graph Algorithm II |
| Characterization of Efficiently Solvable Problems on Distance-Hereditary Graphs / Sun-Yuan Hsieh ; Chin-Wen Ho ; Tsan-Sheng Hsu ; Ming-Tat Ko ; Gen-Huey Chen |
| Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs / Yaw-Ling Lin |
| Finding Planar Geometric Automorphisms in Planar Graphs / Seok-Hee Hong ; Peter Eades ; Sang-Ho Lee |
| Combinatorial Problem |
| A New Approach for Speeding Up Enumeration Algorithms / Takeaki Uno |
| Hamiltonian Decomposition of Recursive Circulants / Jung-Heum Park |
| Convertibility among Grid Filling Curves / Naoki Katoh ; Hisao Tamaki ; Takeshi Tokuyama |
| Geometry II |
| Generalized Self-Approaching Curves / Oswin Aichholzer ; Franz Aurenhammer ; Christian Icking ; Rolf Klein ; Elmar Langetepe ; Günter Rote |
| Computational Biology / Guo-Hui Lin ; Guoliang Xue |
| Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages / Tatsuya Akutsu |
| On the Multiple Gene Duplication Problem / Michael Fellows ; Michael Hallett ; Ulrike Stege |
| Geometry III |
| Visibility Queries in Simple Polygons and Applications / Leonidas J. Guibas ; Marek Teichmann ; Li Zhang |
| Quadtree Decomposition and Steiner Triangulation and Ray Shooting / Kam-Hing Lee |
| Optimality and Integer Programming Formulations of Triangulations in General Dimension / Akira Tajima |
| Approximation Algorithm |
| Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs / Philip N. Klein ; Hsueh-I Lu |
| A Capacitated Vehicle Routing Problem on a Tree / Shin-ya Hamaguchi |
| Approximation Algorithms for Some Optimum Communication Spanning Tree Problems / Bang Ye Wu ; Kun-Mao Chao ; Chuan Yi Tang |
| Complexity III |
| The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees / Xiao Zhou ; Takao Nishizeki |
| Inapproximability Results for Guarding Polygons without Holes / Stephan Eidenbenz |
| The Inapproximability of Non NP-hard Optimization Problems / Liming Cai ; David Juedes ; Iyad Kanj |
| Parallel and Distributed Algorithm |
| An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate / Toru Hasunuma |
| A Parallel Algorithm for Sampling Matchings from an Almost Uniform Distribution / J. Diaz ; J. Petit ; P. Psycharis ; M. Serna |
| Optimal Approximate Agreement with Omission Faults / Richard Plunkett ; Alan Fekete |
| Author Index |
| Invited Presentation |
| The Discrepancy Method / Bernard Chazelle |
| Implementing Algorithms and Data Structures: An Educational and Research Perspective / Roberto Tamassia |
| Geometry I |
| Facility Location on Terrains / Evanthia Papadopoulou ; Boris Aronov ; Marc van Kreveld ; René van Oostrum ; Kasturirangan Varadarajan |
| Computing Weighted Rectilinear Median and Center Set in the Presence of Obstacles / Joonsoo Choi ; Chan-Su Shin ; Sung Kwon Kim |
