Front matter
1-10
Complete Problems for Valiant’s Class of qp-Computable Families of Polynomials
Markus Bläser
11-20
Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(
n
4.03)
Extended Abstract
Michal KouckÝ
21-27
On Universally Polynomial Context-Free Languages
Nicholas Tran
28-38
Separating Oblivious and Non-oblivious BPs
Kazuo Iwama, Yasuo Okabe and Toshiro Takase
39-48
Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws
Iain A. Stewart
49-58
Algebraic Properties for P-Selectivity
Lane A. Hemaspaandra, Harald Hempel⋆ and Arfst Nickelsen
59-63
Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM
Carla Denise Castanho, Wei Chen, Koichi Wada and Akihiro Fujiwara
64-74
Enhanced Sequence Reconstruction with DNA Microarray Application
Extended Abstract
Samuel A. Heath and Franco P. Preparata
75-85
Non-approximability of Weighted Multiple Sequence Alignment
Bodo Siebert
86-90
A Greedy Algorithm for Optimal Recombination
Shiquan Wu and Xun Gu
91-100
Generating Well-Shaped
d
-dimensional Delaunay Meshes
Xiang-Yang Li
101-110
Towards Compatible Triangulations
Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser and Ferran Hurtado
111-120
An Improved Upper Bound on the Size of Planar Convex-Hulls
Abdullah N. Arslan and Ömer Eğecioğlu
121-130
On the Planar Two-Watchtower Problem
Sergei Bespamyatnikh, Zhixiang Chen, Kanliang Wang and Binhai Zhu
131-141
Efficient Generation of Triconnected Plane Triangulations
Shin-ichi Nakano
142-149
Packing Two Disks into a Polygonal Environment
Prosenjit Bose, Pat Morin and Antoine Vigneron
150-158
Maximum Red/Blue Interval Matching with Application
Danny Z. Chen, Xiaobo Sharon Hu and Xiaodong Wu
159-169
Computing Farthest Neighbors on a Convex Polytope
Otfried Cheong, Chan-Su Shin and Antoine Vigneron
170-180
Finding an Optimal Bridge between Two Polygons
Xuehou Tan
181-190
How Good Is Sink Insertion?
Xiang-Yang Li and Yu Wang
191-200
Polynomial Time Algorithms for Three-Label Point Labeling
Rob Duncan, Jianbo Qian and Binhai Zhu
201-206
Approximation Algorithms for the Watchman Route and Zookeeper’s Problems
Xuehou Tan
207-217
PC
-Trees vs.
PQ
-Trees
Wen-Lian Hsu
218-227
Stacks versus Deques
Holger Petersen
228-236
Optimizing a Computational Method for Length Lower Bounds for Reflecting Sequences
H. K. Dai
237-246
Competitive Facility Location along a Highway
Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin and René van Oostrum
247-256
Membership for Core of LP Games and Other Games
Qizhi Fang, Shanfeng Zhu, Maocheng Cai and Xiaotie Deng
257-261
Strong Solutions to the Identification Problem
Pino Caballero-Gil and Candelaria Hernández-Goya
262-267
Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF(2m)1
Hyun-Sung Kim and Kee-Young Yoo
268-277
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms
Valerie King and Mikkel Thorup
278-287
Finding the Most Vital Node of a Shortest Path
Enrico Nardelli, Guido Proietti and Peter Widmayer
288-297
Algorithm for the Cost Edge-Coloring of Trees
Xiao Zhou and Takao Nishizeki
298-307
Counting
H
-Colorings of Partial
k
-Trees
Josep Díaz, Maria Serna and Dimitrios M. Thilikos
308-317
A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph
L. Sunil Chandran
318-327
Graph Separators: A Parameterized View
Jochen Alber, Henning Fernau and Rolf Niedermeier
328-337
On Assigning Prefix Free Codes to the Vertices of a Graph
N. S. Narayanaswamy and C. E. Veni Madhavan
338-348
A New Measure of Edit Distance between Labeled Trees
Chin Lung Lu, Zheng-Yao Su and Chuan Yi Tang
349-356
A Highly Efficient Algorithm to Determine Bicritical Graphs
Dingjun Lou and Ning Zhong
357-367
Layered Drawings of Graphs with Crossing Constraints
Irene Finocchi
368-374
On the Validity of Hierarchical Decompositions
Irene Finocchi and Rossella Petreschi
375-383
Lower Bounds on the Minus Domination and
k
-Subdomination Numbers
Liying Kang, Hong Qiao, Erfang Shan and Ding-Zhu Du
384-389
Edge Connectivity vs Vertex Connectivity in Chordal Graphs
L. Sunil Chandran
390-394
Changing the Diameter of Graph Products
Ting-Yi Sung and Jeng-Jung Wang
395-399
Plane Graphs with Acyclic Complex
Baogang Xu
400-408
On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs
Extended Abstract
Yosuke Kikuchi and Yukio Shibata
409-413
A Notion of Cross-Perfect Bipartite Graphs
Milind Dawande
414-419
Some Results on Orthogonal Factorizations
Haodi Feng
420-431
Cluttered Orderings for the Complete Graph
Myra B. Cohen, Charles J. Colbourn and Dalibor Froncek
432-442
Improved On-Line Stream Merging: From a Restricted to a General Setting
Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting and Wai-Ha Wong
443-452
On-Line Deadline Scheduling on Multiple Resources
Jae-Hoon Kim and Kyung-Yong Chwa
453-462
Competitive Online Scheduling with Level of Service
(Extended Abstract)
Ee-Chien Chang and Chee Yap
463-472
On-Line Variable Sized Covering
Leah Epstein
473-482
On Testing for Zero Polynomials by a Set of Points with Bounded Precision
Jin-Yi Cai and Eric Bach
483-492
A Randomized Algorithm for Gossiping in Radio Networks
Marek Chrobak, Leszek Gąsieniec and Wojciech Rytter
493-501
Deterministic Application of Grover’s Quantum Search Algorithm
Kyoichi Okamoto and Osamu Watanabe
502-508
Random Instance Generation for MAX 3SAT
Extended Abstract
Mitsuo Motoki
509-518
The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner Points
Dingzhu Du, Lusheng Wang and Baogang Xu
519-528
AnFPTAS forWeight-Constrained SteinerTrees in Series-Parallel Graphs
Guangting Chen and Guoliang Xue
529-539
Decidable Approximations on Generalized and Parameterized Discrete Timed Automata
Zhe Dang, Oscar H. Ibarra and Richard A. Kemmerer
540-549
Multiplicative Adaptive Algorithms for User Preference Retrieval
Zhixiang Chen
550-560
Parametric Scheduling for Network Constraints
K. Subramani
561-570
A Logical Framework for Knowledge Sharing in Multi-agent Systems
Kaile Su, Xudong Luo, Huaiqing Wang, Chengqi Zhang and Shichao Zhang, et al.
571-575
A Lockout Avoidance Algorithm without Using Time-Stamps for the
k
-Exclusion Problem
Kumiko Obokata, Michiko Omori, Kazuhiro Motegi and Yoshihide Igarashi
576-585
Prefix-Free Languages and Initial Segments of Computably Enumerable Degrees
Guohua Wu
586-595
Weakly Computable Real Numbers and Total Computable Real Functions
Extended Abstract
Robert Rettinger1, Xizhong Zheng, Romain Gengler and Burchard von Braunmühl
596-599
Turing Computability of a Nonlinear Schrödinger Propagator
Klaus Weihrauch and Ning Zhong
Back matter