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

Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan (auth.), Takano Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, Takeshi Tokuyama (eds.)3540662006, 9783540662006

The abstracts and papers in this volume were presented at the Fifth Annual International Computing and Combinatorics Conference (COCOON ’99), which was held in Tokyo, Japan from July 26 to 28, 1999. The topics cover most aspects of theoretical computer science and combinatorics pertaining to computing. In response to the call for papers, 88 high-quality extended abstracts were submitted internationally, of which 46 were selected for presentation by the p- gram committee. Every submitted paper was reviewed by at least three program committee members. Many of these papers represent reports on continuing – search, and it is expected that most of them will appear in a more polished and complete form in scienti c journals. In addition to the regular papers, this v- ume contains abstracts of two invited plenary talks by Prabhakar Raghavan and Seinosuke Toda. The conference also included a special talk by Kurt Mehlhorn on LEDA (Library of E cient Data types and Algorithms). The Hao Wang Award (inaugurated at COCOON ’97) is given to honor the paper judged by the program committee to have the greatest scienti c merit. The recipients of the Hao Wang Award 1999 were Hiroshi Nagamochi and Tos- hide Ibaraki for their paper An Approximation for Finding a Smallest 2-Edge- Connected Subgraph Containing a Speci ed Spanning Tree”.

---

Table of contents :
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