| The Complexity of Mean Payoff Games | p. 1 |
| Approximation of coNP Sets by NP-Complete Sets | p. 11 |
| How to Draw a Planar Clustered Graph | p. 21 |
| An Efficient Orthogonal Grid Drawing Algorithm for Cubic Graphs | p. 31 |
| Constrained Independence System and Triangulations of Planar Point Sets | p. 41 |
| Three Dimensional Weak Visibility: Complexity and Applications | p. 51 |
| Rectangulating Rectilinear Polygons in Parallel | p. 61 |
| Efficient Randomized Incremental Algorithm for the Closest Pair Problem Using Leafary Trees | p. 71 |
| Testing Containment of Object-Oriented Conjunctive Queries Is [actual symbol not reproducible] | p. 81 |
| Computing Infinite Relations Using Finite Expressions: a New Approach to the Safety Issue in Relational Databases | p. 91 |
| Set-Term Unification in a Logic Database Language | p. 101 |
| Computations with Finite Closure Systems and Implications | p. 111 |
| Maximum Tree-Packing in Time O(n[superscript 5/2]) | p. 121 |
| Optimal Algorithms for Finding Connected Components of an Unknown Graph | p. 131 |
| The Multi-Weighted Spanning Tree Problem | p. 141 |
| Algorithmic Graph Embeddings | p. 151 |
| Analysis of Quorum-Based Protocols for Distributed (k + 1)-Exclusion | p. 161 |
| A Highly Fault-Tolerant Quorum Consensus Method for Managing Replicated Data | p. 171 |
| Constructing Craig Interpolation Formulas | p. 181 |
| Currying of Order-Sorted Term Rewriting Systems | p. 191 |
| Stack and Queue Number of 2-Trees | p. 203 |
| Shortest Paths in Random Weighted Graphs | p. 213 |
| Simple Reduction of f-Colorings to Edge-Colorings | p. 223 |
| Output-Size Sensitiveness of OBDD Construction Through Maximal Independent Set Problem | p. 229 |
| Small Weight Bases for Hamming Codes | p. 235 |
| Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms | p. 244 |
| A Construction for Enumerating k-Coloured Motzkin Paths | p. 254 |
| On Public-Key Cryptosystem Based on Church-Rosser String-Rewriting Systems | p. 264 |
| Extending the Hong-Kung Model to Memory Hierarchies | p. 270 |
| On Log-Time Alternating Turing Machines of Alternating Depth k | p. 282 |
| New Bound for Affine Resolvable Designs and Its Application to Authentication Codes | p. 292 |
| Dense Packings of 3k(k + 1) + 1 Equal Disks in a Circle for k = 1,2,3,4, and 5 | p. 303 |
| Efficient Parallel Algorithms for Some Tree Layout Problems | p. 313 |
| Conservative Algorithms for Parallel and Sequential Integer Sorting | p. 324 |
| An Optimal Algorithm for Proper Learning of Unions of Two Rectangles with Queries | p. 334 |
| Disjunctions of Negated Counting Functions Are Efficiently Learnable with Equivalence Queries | p. 344 |
| Non-Empty Cross-3-Intersection Theorems of Subsets | p. 350 |
| Convexity of Minimal Total Dominating Functions in Graphs | p. 357 |
| Transformations for Maximal Planar Graphs with Minimum Degree Five | p. 366 |
| An Asynchronous Parallel Method for Linear Systems | p. 372 |
| On a Kind of Sequence of Polynomials | p. 379 |
| Hamiltonian Cycles in 2-Generated Cayley Digraphs of Abelian Groups | p. 384 |
| Pandiagonal Magic Squares | p. 388 |
| PFFM and Quasi-Morishima Matrices | p. 392 |
| Edge-Face Total Chromatic Number of Outerplanar Graphs with [Delta](G) = 6 | p. 396 |
| Sets Computable in Polynomial Time on Average | p. 400 |
| Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions | p. 410 |
| Transformations That Preserve Malignness of Universal Distributions | p. 420 |
| Intersection Suffices for Boolean Hierarchy Equivalence | p. 430 |
| A 3/2log 3-Competitive Algorithm for the Counterfeit Coin Problem | p. 436 |
| Searching Rigid Data Structures | p. 446 |
| A Better Subgraph of the Minimum Weight Triangulation | p. 452 |
| Sequence Decomposition Method for Computing a Grobner Basis and Its Application to Bivariate Splines | p. 456 |
| A Broadcasting Algorithm on the Arrangement Graph | p. 462 |
| A Fast Maximum Finding Algorithm on Broadcast Communication | p. 472 |
| Broadcasting in General Networks I: Trees | p. 482 |
| Uni-Directional Alternating Group Graphs | p. 490 |
| On Separating Proofs of Knowledge from Proofs of Membership of Languages and Its Application to Secure Identification Schemes | p. 496 |
| Compact Location Problems with Budget and Communication Constraints | p. 510 |
| Minimum Dominating Sets of Intervals on Lines | p. 520 |
| Two-Dimensional Pattern Matching on a Dynamic Library of Texts | p. 530 |
| Structure in Approximation Classes | p. 539 |
| Improved Lower Bounds for the Randomized Boppana-Halldorsson Algorithm for MAXCLIQUE | p. 549 |
| MNP: A Class of NP Optimization Problems | p. 559 |
| Semidefinite Programming and Its Applications to NP Problems | p. 566 |
| Analysis and Experimentation on List Update Algorithms | p. 576 |
| An Exact Branch and Bound Algorithm for the Steiner Problem in Graphs | p. 582 |
| A Physical Model for the Satisfiability Problem | p. 591 |
| An Efficient Algorithm for Local Testability Problem of Finite State Automata | p. 597 |
| Scheduling Task-Tree with Additive Scales on Parallel/ Distributed Machines | p. 607 |
| Single-Vehicle Scheduling Problem on a Straight Line with Time Window Constraints | p. 617 |
| An On-Line Algorithm for Some Uniform Processor Scheduling | p. 627 |
| An Algebraic Characterization of Tractable Constraints | p. 633 |
| Limit Property of Unbalanced Development in Economic Network | p. 643 |
| Document Processing, Theory, and Practice | p. 647 |
| Matching and Comparing Sequences in Molecular Biology | p. 648 |
| Primal-Dual Schema Based Approximation Algorithms | p. 650 |
| Author Index | p. 653 |
| Table of Contents provided by Blackwell. All Rights Reserved. |
