Front matter
1-2
Theoretical Problems Related to the Internet
Extended Abstract
Christos H. Papadimitriou
3-22
Recent Progress and Prospects for Integer Factorisation Algorithms
Richard P. Brent
23-33
Approximating Uniform Triangular Meshes in Polygons
Franz Aurenhammer, Naoki Katoh, Hiromichi Kojima, Makoto Ohsaki and Yinfeng Xu
34-43
Maximum Induced Matchings of Random Cubic Graphs
William Duckworth, Nicholas C. Wormald and Michele Zito
44-53
A Duality between Small-Face Problems in Arrangements of Lines and Heilbronn-Type Problems
Gill Barequet
54-63
On Local Transformation of Polygons with Visibility Properties
Carmen Hernando, Michael E. Houle and Ferran Hurtado
64-73
Embedding Problems for Paths with Direction Constrained Edges
Giuseppe Di Battista, Giuseppe Liotta, Anna Lubiw and Sue Whitesides
74-84
Characterization of Level Non-planar Graphs by Minimal Patterns
Patrick Healy, Ago Kuusik and Sebastian Leipert
85-94
Rectangular Drawings of Plane Graphs Without Designated Corners
Extended Abstract
Md. Saidur Rahman, Shin-ichi Nakano and Takao Nishizeki
95-104
Computing Optimal Embeddings for Planar Graphs
Petra Mutzel and René Weiskircher
105-114
Approximation Algorithms for Independent Sets in Map Graphs
Zhi-Zhong Chen
115-125
Hierarchical Topological Inference on Planar Disc Maps
Zhi-Zhong Chen and Xin He
126-136
Efficient Algorithms for the Minimum Connected Domination on Trapezoid Graphs
Yaw-Ling Lin, Fang Rong Hsu and Yin-Te Tsai
137-147
Parameterized Complexity of Finding Subgraphs with Hereditary Properties
Subhash Khot and Venkatesh Raman
148-158
Some Results on Tries with Adaptive Branching
Yuriy A. Reznik
159-169
Optimal Coding with One Asymmetric Error: Below the Sphere Packing Bound
Ferdinando Cicalese and Daniele Mundici
170-179
Closure Properties of Real Number Classes under Limits and Computable Operators
Xizhong Zheng
180-192
A Characterization of Graphs with Vertex Cover Six
Michael J. Dinneen and Liu Xiong
193-201
On the Monotonicity of Minimum Diameter with Respect to Order and Maximum Out-Degree
Mirka Miller and Slamin
202-209
Online Independent Sets
Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi
210-220
Two-Dimensional On-Line Bin Packing Problem with Rotatable Items
Satoshi Fujita and Takeshi Hada
221-231
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem
Extended Abstract
Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen and Guo-Hui Lin
232-241
Ordinal On-Line Scheduling on Two Uniform Machines
Zhiyi Tan and Yong He
242-251
Agents, Distributed Algorithms, and Stabilization
Sukumar Ghosh
252-261
A Fast Sorting Algorithm and Its Generalization on Broadcast Communications
Shyue-Horng Shiau and Chang-Biau Yang
262-271
Efficient List Ranking Algorithms on Reconfigurable Mesh
Sung-Ryul Kim and Kunsoo Park
272-280
Tripods Do Not Pack Densely
Alexandre Tiskin
281-290
An Efficient
k
Nearest Neighbor Searching Algorithm for a Query Line
Subhas C. Nandy
291-298
Tetrahedralization of Two Nested Convex Polyhedra
Cao An Wang and Boting Yang
299-309
Efficient Algorithms for Two-Center Problems for a Convex Polygon
Extended Abstract
Sung Kwon Kim and Chan-Su Shin
310-319
On Computation of Arbitrage for Markets with Friction
Xiaotie Deng, Zhongfei Li and Shouyang Wang
320-329
On Some Optimization Problems in Obnoxious Facility Location
Zhongping Qin, Yinfeng Xu and Binhai Zhu
330-339
Generating Necklaces and Strings with Forbidden Substrings
Frank Ruskey and Joe Sawada
340-350
Optimal Labelling of Point Features in the Slider Model
Extended Abstract
Gunnar W. Klau and Petra Mutzel
351-361
Mappings for Conflict-Free Access of Paths in Elementary Data Structures
Alan A. Bertossi and M. Cristina Pinotti
362-372
Theory of Trinomial Heaps
Tadao Takaoka
373-382
Polyhedral Aspects of the Consecutive Ones Problem
Marcus Oswald and Gerhard Reinelt
383-395
The Complexity of Physical Mapping with Strict Chimerism
Stephan Weis and Rüdiger Reischuk
396-406
Logical Analysis of Data with Decomposable Structures
Hirotaka Ono, Kazuhisa Makino and Toshihide Ibaraki
407-415
Learning from Approximate Data
Shirley Cheung H.C.
416-425
A Combinatorial Approach to Asymmetric Traitor Tracing
Reihaneh Safavi-Naini and Yejing Wang
426-435
Removing Complexity Assumptions from Concurrent Zero-Knowledge Proofs
Extended Abstract
Giovanni Di Crescenzo
436-446
One-Way Probabilistic Reversible and Quantum One-Counter Automata
Tomohiro Yamasaki, Hirotada Kobayashi, Yuuki Tokunaga and Hiroshi Imai
447-456
Similarity Enrichment in Image Compression through Weighted Finite Automata
Zhuhan Jiang, Bruce Litow and Olivier de Vel
457-466
On the Power of Input-Synchronized Alternating Finite Automata
Hiroaki Yamamoto
467-476
Ordered Quantum Branching Programs Are More Powerful than Ordered Probabilistic Branching Programs under a Bounded-Width Restriction
Masaki Nakanishi, Kiyoharu Hamaguchi and Toshinobu Kashiwabara
Back matter