Computing and Combinatorics: 5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings

The Web as a Graph: Measurements, Models, and Methods....Pages 1-17
Some Observations on the Computational Complexity of Graph Accessibility Problem (Extended Abstract)....Pages 18-30
An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree....Pages 31-40
Theory of 2-3 Heaps....Pages 41-50
An External Memory Data Structure for Shortest Path Queries (Extended Abstract)....Pages 51-60
Approximating the Nearest Neighbor Interchange Distance for Evolutionary Trees with Non-uniform Degrees....Pages 61-70
Signed Genome Rearrangement by Reversals and Transpositions: Models and Approximations....Pages 71-80
An Approximation Algorithm for the Two-Layered Graph Drawing Problem....Pages 81-91
Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs....Pages 92-102
Layout Problems on Lattice Graphs....Pages 103-112
A New Transference Theorem in the Geometry of Numbers....Pages 113-122
On Covering and Rank Problems for Boolean Matrices and Their Applications....Pages 123-133
A Combinatorial Algorithm for Pfaffians....Pages 134-143
How to Swap a Failing Edge of a Single Source Shortest Paths Tree....Pages 144-153
On Bounds for the k -Partitioning of Graphs....Pages 154-163
A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs....Pages 164-173
Probabilities to Accept Languages by Quantum Finite Automata....Pages 174-183
Distributionally-Hard Languages....Pages 184-193
Circuits and Context-Free Languages....Pages 194-203
On the Negation-Limited Circuit Complexity of Merging....Pages 204-209
Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy....Pages 210-220
Efficient Learning of Some Linear Matrix Languages....Pages 221-230
Minimizing Mean Response Time in Batch Processing System....Pages 231-240
Approximation Algorithms for Bounded Facility Location....Pages 241-250
Scheduling Trees onto Hypercubes and Grids Is NP -complete....Pages 251-260
Approximations of Weighted Independent Set and Hereditary Subset Problems....Pages 261-270
Multi-coloring Trees....Pages 271-280
On the Complexity of Approximating Colored-Graph Problems Extended Abstract....Pages 281-290
On the Average Sensitivity of Testing Square-Free Numbers....Pages 291-299
Binary Enumerability of Real Numbers (Extended Abstract)....Pages 300-309
GCD of Many Integers (Extended Abstract)....Pages 310-317
Multi-party Finite Computations....Pages 318-329
Probabilistic Local Majority Voting for the Agreement Problem on Finite Graphs....Pages 330-338
A Dynamic-Programming Bound for the Quadratic Assignment Problem....Pages 339-348
A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases....Pages 349-359
On Routing in Circulant Graphs....Pages 360-369
Minimum Congestion Embedding of Complete Binary Trees into Tori....Pages 370-378
Maximum Stabbing Line in 2D Plane....Pages 379-388
Generalized Shooter Location Problem....Pages 389-399
A Competitive Online Algorithm for the Paging Problem with “Shelf” Memory....Pages 400-408
Using Generalized Forecasts for Online Currency Conversion....Pages 409-421
On S-Regular Prefix-Rewriting Systems and Automatic Structures....Pages 422-431
Tractable and Intractable Second-Order Matching Problems....Pages 432-441
Efficient Fixed-Size Systolic Arrays for the Modular Multiplication....Pages 442-451
Improving Parallel Computation with Fast Integer Sorting....Pages 452-461
A Combinatorial Approach to Performance Analysis of a Shared-Memory Multiprocessor....Pages 462-472
A Fast Approximation Algorithm for TSP with Neighborhoods and Red-Blue Separation....Pages 473-482
The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set....Pages 483-492