Front matter
59-188
Voronoi-Based Systems of Coordinates and Surface Reconstruction
Jean-Daniel Boissonnat
225-274
Essentially Every Unimodular Matrix Defines an Expander
Jin-Yi Cai
1-18
Strategies for Hotlink Assignments
Prosenjit Bose, Jurek Czyzowicz, Leszek Gąsieniec, Evangelos Kranakis and Danny Krizanc, et al.
265-266
A New Competitive Analysis of Randomized Caching
(Extended Abstract)
Ching Law and Charles E. Leiserson
1-90
Online Routing in Convex Subdivisions
Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Erik D. Demaine and Rudolf Fleischer, et al.
349-367
A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors
Jingui Huang, Jianer Chen and Songqiao Chen
72-83
Classification of Various Neighborhood Operations for the Nurse Scheduling Problem
(Extended Abstract)
Takayuki Osogami and Hiroshi Imai
1-26
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets
Yuyu Chen, Ming-Yang Kao and Hsueh-I. Lu
269-293
Coping with Delays and Time-Outs in Binary Search Procedures
Ferdinando Cicalese and Ugo Vaccaro
129-150
Some Formal Analysis of Rocchio’s Similarity-Based Relevance Feedback Algorithm
Zhixiang Chen and Binhai Zhu
177-212
Reasoning with Ordered Binary Decision Diagrams
Takashi Horiyama and Toshihide Ibaraki
19-58
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching
Jianer Chen and Iyad A. Kanj
79-91
A 2-Approximation Algorithm for Path Coloring on Trees of Rings
Xiaotie Deng, Guojun Li, Wenan Zang and Yi Zhou
263-309
An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree
Q. S. Wu, C. L. Lu and R. C. T. Lee
321-356
Finding Independent Spanning Trees in Partial
k
-Trees
Xiao Zhou and Takao Nishizeki
253-290
On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover
Rolf Niedermeier and Peter Rossmanith
192-203
Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width
Dimitrios M. Thilikos, Maria J. Serna and Hans L. Bodlaender
105-141
Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits
Takao Asano, Magnús M. Halldórsson, Kazuo Iwama and Takeshi Matsuda
41-100
A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane
Norihiro Kubo, Katsuhiro Muramoto and Shinichi Shimozono
247-262
Simple Algorithms for a Weighted Interval Selection Problem
Thomas Erlebach and Frits C.R. Spieksma
267-269
Efficient Minus and Signed Domination in Graphs
Chin Lung Lu, Sheng-Lung Peng and Chuan Yi Tang
143-188
Convex Grid Drawings of Four-Connected Plane Graphs
(Extended Abstract)
Kazuyuki Miura, Shin-ichi Nakano and Takao Nishizeki
266-277
An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs
Seok-Hee Hong and Peter Eades
399-443
Undecidability Results for Monoids with Linear-Time Decidable Word Problems
Masashi Katsura, Yuji Kobayashi and Friedrich Otto
7-39
Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures
Reina Yoshikawa, Shimin Guo, Kazuhiro Motegi and Yoshihide Igarashi1
1-5
Derandomizing Arthur-Merlin Games under Uniform Assumptions
Chi-Jen Lu
189-224
A Near Optimal Algorithm for Vertex Connectivity Augmentation
Bill Jackson and Tibor Jordán
151-170
Simultaneous Augmentation of Two Graphs to an
ℓ
Edge-Connected Graph and a Biconnected Graph
Toshimasa Ishii and Hiroshi Nagamochi
338-349
Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets
Hiro Ito, Motoyasu Ito, Yuichiro Itatsu, Hideyuki Uehara and Mitsuo Yokoyama
213-241
An Intuitive and Effective New Representation for Interconnection Network Structures
Jianer Chen, Lihua Liu, Weijia Jia and Songqiao Chen
101-213
Randomized Leader Election Protocols in Radio Networks with no Collision Detection
Koji Nakano and Stephan Olariu
243-268
Deterministic Broadcasting Time with Partial Knowledge of the Network
Gianluca De Marco and Andrzej Pelc
189-234
Minimizing Makespan in Batch Machine Scheduling
Chung Keung Poon and Pixing Zhang
1-45
Preemptive Parallel Task Scheduling in
O
(
n
) + Poly(
m
) Time
Klaus Jansen and Lorant Porkolab
295-321
Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array
Kunihiko Sadakane
257-263
A Better Lower Bound for Two-Circle Point Labeling
Alexander Wolff, Michael Thon and Yinfeng Xu
91-141
Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set
Deok-Soo Kim, Donguk Kim and Kokichi Sugihara
47-104
An Improved Algorithm for Subdivision Traversal without Extra Storage
Prosenjit Bose and Pat Morin
215-256
Generalized
H
-Coloring of Graphs
Petter Kristiansen and Jan Arne Telle
93-127
Finding a Two-Core of a Tree in Linear Time
Biing-Feng Wang and Jyh-Jye Lin
323-335
Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung and Hing-Fung Ting
143-175
Optimal Beam Penetrations in Two and Three Dimensions
Danny Z. Chen, Xiaobo Hu and Jinhui Xu
275-319
Searching a Simple Polygon by a
k
-Searcher
Xuehou Tan
337-347
Characterization of Rooms Searchable by Two Guards
Sang-Min Park, Jae-Ha Lee and Kyung-Yong Chwa
369-382
Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers
Wing-Kai Hon, Ming-Yang Kao and Tak-Wah Lam
291-398
Phylogenetic
k
-Root and Steiner
k
-Root
Guo-Hui Lin, Paul E. Kearney and Tao Jiang
213-245
Maintenance of a Piercing Set for Intervals with Applications
Matthew J. Katz, Frank Nielsen and Michael Segal
564-576
Optimal Polygon Cover Problems and Applications
Danny Z. Chen, Xiaobo Hu and Xiaodong Wu
Back matter