Front matter
1-13
Chain Reconfiguration The Ins and Outs, Ups and Downs of Moving Polygons and Polygonal Linkages
Sue Whitesides
14-25
Application of M-Convex Submodular Flow Problem to Mathematical Economics
Kazuo Murota and Akihisa Tamura
26-35
A Polynomial Time Approximation Scheme for Minimizing Total Completion Time of Unbounded Batch Scheduling
Xiaotie Deng, Haodi Feng, Pixing Zhang and Hong Zhu
36-48
A Polynomial Time Approximation Scheme for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times
Yoshiyuki Karuno and Hiroshi Nagamochi
48-60
Semi-normal Schedulings: Improvement on Goemans’ Algorithm
Jianer Chen and Jingui Huang
61-73
Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
Hisashi Koga
74-85
Broadcasting with Universal Lists Revisited: Using Competitive Analysis
Jae-Hoon Kim and Kyung-Yong Chwa
86-98
On Adaptive Fault Diagnosis for Multiprocessor Systems
Kumiko Nomura, Toshinori Yamada and Shuichi Ueno
99-106
On-Line Multicasting in All-Optical Networks
Kenta Hashimoto, Toshinori Yamada and Shuichi Ueno
107-115
Enumerating Floorplans with n Rooms
Shin-ichi Nakano
116-123
On Min-Max Cycle Bases
Giulia Galbiati
124-135
On the Minimum Local-Vertex-Connectivity Augmentation in Graphs
Hiroshi Nagamochi and Toshimasa Ishii
136-147
Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number
Takayuki Nagoya
148-159
Quantum Algorithms for Intersection and Proximity Problems
Kunihiko Sadakane, Norito Sugawara and Takeshi Tokuyama
160-171
BUSHWHACK: An Approximation Algorithm for Minimal Paths through Pseudo-Euclidean Spaces
Zheng Sun and John Reif
172-184
Approximation of Minimum Triangulation for Polyhedron with Bounded Degrees
Francis Y. L. Chin and Stanley P. Y. Fung
185-195
Tree-Approximations for the Weighted Cost-Distance Problem
(Extended Abstract)
Christian Schindelhauer and Birgitta Weber
196-207
Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups
(Extended Abstracts)
Takaaki Mizuki and Takao Nishizeki
208-218
Generic Algorithms and Key Agreement Protocols Based on Group Actions
Akihiro Yamamura and Kaoru Kurosawa
219-230
Baire Category and Nowhere Differentiability for Feasible Real Functions
Josef M. Breutzmann, David W. Juedes and Jack H. Lutz
231-243
Translation among CNFs, Characteristic Models and Ordered Binary Decision Diagrams
Takashi Horiyama and Toshihide Ibaraki
244-256
On Removing the Pushdown Stack in Reachability Constructions
Oscar H. Ibarra and Zhe Dang
257-267
A New Recognition Algorithm for Extended Regular Expressions
Hiroaki Yamamoto
268-278
Polynomial-Time Algorithms for the Equivalence for One-Way Quantum Finite Automata
Takeshi Koshiba
279-290
An Index for the Data Size to Extract Decomposable Structures in LAD
Hirotaka Ono, Mut unori Yagiura and Toshihide Ibaraki
291-307
Parameterized Complexity: The Main Ideas and Some Research Frontiers
Michael R. Fellows
308-319
Tight Bounds on Maximal and Maximum Matchings
Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer and Stephen G. Kobourov
320-331
Recognition and Orientation Algorithms for P4-Comparability Graphs
Stavros D. Nikolopoulos and Leonidas Palios
332-344
Efficient Algorithms for k-Terminal Cuts on Planar Graphs
Danny Z. Chen and Xiaodong Wu
345-354
Polynomial Time Algorithms for Edge-Connectivity Augmentation of Hamiltonian Paths
Anna Galluccio and Guido Proietti
355-367
Algorithms for Pattern Involvement in Permutations
Michael H. Albert, Robert E. L. Aldred, Mike D. Atkinson and Derek A. Holton
367-379
A Fast Algorithm for Enumerating Bipartite Perfect Matchings
Takeaki Uno
380-389
On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time
Bo Chen, Xiaotie Deng and Wenan Zang
390-402
On the Complexity of Train Assignment Problems
Thomas Erlebach, Martin Gantenbein, Daniel Hürlimann, Gabriele Neyer and Aris Pagourtzis, et al.
403-415
A Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model
James Aspnes, Julia Hartling, Kao Ming-Yang, Junhyong Kim and Gauri Shah
416-428
Complexity of Comparing Hidden Markov Models
Rune B. Lyngsø and Christian N. S. Pedersen
429-441
DNA Self-Assembly For Constructing 3D Boxes
(Extended Abstract)
Kao Ming-Yang and Vijay Ramachandran
441-453
Exact Solutions for Closest String and Related Problems
Jens Gramm, Rolf Niedermeier and Peter Rossmanith
454-466
Topological Peeling and Implementation
Danny Z. Chen, Shuang Luan and Jinhui Xu
467-479
Image Segmentation with Monotonicity and Smoothness Constraints
Danny Z. Chen, Jie Wang and Xiaodong Wu
480-492
Optimization Algorithms for Sweeping a Polygonal Region with Mobile Guards
Lee Jae-Ha, Park Sang-Min and Chwa Kyung-Yong
493-501
Approximation of a Geometric Set Covering Problem
Sofia Kovaleva and Frits C. R. Spieksma
502-513
Shortest Path Algorithms: Engineering Aspects
Andrew V. Goldberg
514-524
Efficient Algorithms for Weighted Colorings of Series-Parallel Graphs
Xiao Zhou and Takao Nishizeki
525-537
Go with the Winners Algorithms for Cliques in Random Graphs
Marcus Peinado
537-549
Complexity of Partial Covers of Graphs
Jiří Fiala and Jan Kratochvíl
550-561
On Game-Theoretic Models of Networks
Hans L. Bodlaender, Michael J. Dinneen and Bakhadyr Khoussainov
562-574
The Complexity of Some Basic Problems for Dynamic Process Graphs
Andreas Jakoby and Maciej Liśkiewicz
575-586
Delay Optimizations in Quorum Consensus
Xuemin Lin
587-599
Randomized Shared Queues Applied to Distributed Optimization Algorithms
Hyunyoung Lee and Jennifer L. Welch
599-609
Multiprocess Time Queue
Andrej Brodnik and Johan Karlsson
610-622
Labeling Points with Weights
Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk and Alexander Wolff
623-635
Small Convex Quadrangulations of Point Sets
David Bremner, Ferran Hurtado, Suneeta Ramaswami and Vera Sacristán
636-648
How to Color a Checkerboard with a Given Distribution — Matrix Rounding Achieving Low 2 × 2-Discrepancy
Tetsuo Asano and Takeshi Tokuyama
649-659
Labeling Subway Lines
Mari Ángeles Garrido, Claudia Iturriaga, Alberto Márquez, José Ramón Portillo and Pedro Reyes, et al.
660-669
Complexity Study on Two Clustering Problems
Extended Abstract
Louxin Zhang and Song Zhu
670-681
A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2
Toshihiro Fujito and Tsuyoshi Okumura
682-694
A Unified Framework for Approximating Multiway Partition Problems
Extended Abstract
Liang Zhao, Hiroshi Nagamochi and Toshihide Ibaraki
695-706
On-Line Algorithms for Cardinality Constrained Bin Packing Problems
Luitpold Babel, Bo Chen, Hans Kellerer and Vladimir Kotov
707-718
Suffix Vector: A Space-Efficient Suffix Tree Representation
Krisztián Monostori, Arkady Zaslavsky and István Vajk
719-730
Fragmentary Pattern Matching: Complexity, Algorithms and Applications for Analyzing Classic Literary Works
Hideaki Hori, Shinichi Shimozono, Masayuki Takeda and Ayumi Shinohara
731-742
Computing the Quartet Distance between Evolutionary Trees in Time O(n log2n)
Gerth Stølting Brodal, Rolf Fagerberg and Christian N. S. Pedersen
743-755
The Cent-dian Path Problem on Tree Networks
Ronald I. Becker, Yen-I Chiang, Isabella Lari and Andrea Scozzari
756-767
Approximate Hotlink Assignment
Evangelos Kranakis, Danny Krizanc and Sunil Shende
768-778
Efficient Algorithms for Two Generalized 2-Median Problems on Trees
Shan-Chyun Ku, Chi-Jen Lu, Biing-Feng Wang and Tzu-Chin Lin
Back matter