Invited Presentations |
Voronoi-Based Systems of Coordinates and Surface Reconstruction / Jean-Daniel Boissonnat |
Essentially Every Unimodular Matrix Defines an Expander / Jin-Yi Cai |
Algorithms and Data Structures (I) |
Strategies for Hotlink Assignments / Prosenjit Bose ; Evangelos Kranakis ; Danny Krizanc ; Jurek Czyzowicz ; Andrzej Pelc ; Leszek Gasieniec ; Miguel V. Martin |
A New Competitive Analysis of Randomized Caching / Ching Law ; Charles E. Leiserson |
Online Routing in Convex Subdivisions / Pat Morin ; Andrej Brodnik ; Svante Carlsson ; Erik D. Demaine ; Rudolf Fleischer ; J. Ian Munro ; Alejandro López-Ortiz |
Combinatorial Optimization |
A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors / Jingui Huang ; Jianer Chen ; Songqiao Chen |
Classification of Various Neighborhood Operations for the Nurse Scheduling Problem / Takayuki Osogami ; Hiroshi Imai |
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets / Yuyu Chen ; Ming-Yang Kao ; Hsueh-I. Lu |
Algorithms and Data Structures (II) |
Coping with Delays and Time-Outs in Binary Search Procedures / Ferdinando Cicalese ; Ugo Vaccaro |
Some Formal Analysis of Rocchio's Similarity-Based Relevance Feedback Algorithm / Zhixiang Chen ; Binhai Zhu |
Reasoning with Ordered Binary Decision Diagrams / Takashi Horiyama ; Toshihide Ibaraki |
Approximation and Randomized Algorithms (I) |
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching / Iyad A. Kanj |
A 2-Approximation Algorithm for Path Coloring on Trees of Rings / Xiaotie Deng ; Yi Zhou ; Guojun Li ; Wenan Zang |
An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree / Q. S. Wu ; C. L. Lu ; R. C. T. Lee |
Algorithms and Data Structures (III) |
Finding Independent Spanning Trees in Partial k-Trees / Xiao Zhou ; Takao Nishizeki |
On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover / Rolf Niedermeier ; Peter Rossmanith |
Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width / Dimitros M. Thilikos, Maria J. Serna ; Hans L. Bodlaender |
Approximation and Randomized Algorithms (II) |
Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits / Takao Asano ; Magnús M. Halldórsso ; Kazuo Iwama ; Takeshi Matsuda |
A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane / Norihiro Kubo ; Shinichi Shimozono ; Katsuhiro Muramoto |
Simple Algorithms for a Weighted Interval Selection Problem / Thomas Erlebach ; Frits C. R. Spieksma |
Graph Drawing and Algorithms |
Efficient Minus and Signed Domination in Graphs / Chin L. Lu ; Sheng-Lung Peng ; Chuan Y. Tang |
Convex Grid Drawings of Four-Connected Plane Graphs / Kazuyuki Miura ; Shin-ichi Nakano |
An Algorithm for Finding Three-Dimensional Symmetry in Series-Parallel Digraphs / Seok-Hee Hong ; Peter Eades |
Automata, Cryptography, and Complexity Theory |
Undecidability Results for Monoids with Linear-Time Decidable Word Problems / Masashi Katsura ; Yuji Kobayashi ; Friedrich Otto |
Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures / Reina Yoshikawa ; Shimin Guo ; Kazuhiro Motegi ; Yoshihide Igarashi |
Derandomizing Arthur-Merlin Games under UniformAssumptions / Chi-Jen Lu |
Algorithms and Data Structures (IV) |
A Near Optimal Algorithm for Vertex Connectivity Augmentation / Bill Jackson ; Tibor Jordan |
Simultaneous Augmentation of Two Graphs to an l-Edge-Connected Graph and a Biconnected Graph / Toshimasa Ishii ; Hiroshi Nagamoch |
Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets / Hiro Ito ; Yuichiro Itatsu ; Hideyuki Uehara ; Mitsuo Yokoyama ; otoyasu Ito (Hitachi, Ltd.) |
Parallel and Distributed Algorithms |
An Intuitive and Effective New Representation for Interconnection Network Structures / Lihua Liu ; Weijia Jia |
Randomized Leader Election Protocols in Radio Networks with no Collision Detection / Koji Nakano ; Stephan Olari |
Deterministic Broadcasting Time with Partial Knowledge of the Network . / Gianluca De Marco |
Algorithms and Data Structures (V) |
Minimizing Makespan in Batch Machine Scheduling / Chung K Poon ; Pixing Zhang |
Preemptive Parallel Task Scheduling in O(n) + Poly(m) Time / Klaus Jansen ; Lorant Porkolab |
Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array / Kunihiko Sadakane |
Computational Geometry (I) |
A Better Lower Bound for Two-Circle Point Labeling / Alexander Wolff ; Michael Thon ; Yinfeng Xu |
Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set / Deok-So Kim ; Donguk Kim ; Kokichi Sugihara |
An Improved Algorithm for Subdivision Traversal without Extra Storage |
Algorithms and Data Structures (VI) |
Generalized H-Coloring of Graphs / Petter Kristiansen ; Jan A. Telle |
Finding a Two-Core of a Tree in Linear Time / Biing-Fing Wang ; Jyh-Jye Lin |
Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison / Tak-Wah Lam ; Wing-Kin Sung ; Hing-Fung Ting |
Computational Geometry (II) |
Optimal Beam Penetrations in Two and Three Dimensions / Danny Z. Chen ; Xiaobo S. Hu ; Jinhui Xu |
Searching a Simple Polygon by a k-Searcher / Xuehou Tan |
Characterization of Rooms Searchable by Two Guards / Sang-Min Park ; Kyung-Yong Chwa ; Jae-Ha Lee |
Computational Biology |
Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers Wing-Kai Hon |
Phylogenetic k-Root and Steiner k-Root / Guo-Hui Lin ; Tao Jiang ; Paul E. Kearney |
Computational Geometry (III) |
Maintenance of a Piercing Set for Intervals with Applications / Matthew J. Katz ; Frank Nielsen ; Michael Segal |
Optimal Polygon Cover Problems and Applications / Xiaodong Wu |
Author Index |
Invited Presentations |
Voronoi-Based Systems of Coordinates and Surface Reconstruction / Jean-Daniel Boissonnat |
Essentially Every Unimodular Matrix Defines an Expander / Jin-Yi Cai |
Algorithms and Data Structures (I) |
Strategies for Hotlink Assignments / Prosenjit Bose ; Evangelos Kranakis ; Danny Krizanc ; Jurek Czyzowicz ; Andrzej Pelc ; Leszek Gasieniec ; Miguel V. Martin |
A New Competitive Analysis of Randomized Caching / Ching Law ; Charles E. Leiserson |