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 |