## Computing and Combinatorics: 5th Annual International Conference, COCOON'99, Tokyo, Japan, July 26-28, 1999, ProceedingsTakao Asano, Hiroshi Imai, D.T. Lee, Shin-ichi Nakano, Takeshi Tokuyama 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". |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Measurements Models and Methods | 1 |

Some Observations on the Computational Complexity of Graph Accessibility Problem Extended Abstract | 18 |

An Approximation for Finding a Smallest 2EdgeConnected Subgraph Containing a Specified Spanning Tree | 31 |

Theory of 23 Heaps | 41 |

An External Memory Data Structure for Shortest Path Queries Extended Abstract | 51 |

Approximating the Nearest Neighbor Interchange Distance for Evolutionary Trees with Nonuniform Degrees | 61 |

Models and Approximations | 71 |

An Approximation Algorithm for the TwoLayered Graph Drawing Problem | 81 |

Approximations of Weighted Independent Set and Hereditary Subset Problems | 261 |

Multicoloring Trees | 271 |

On the Complexity of Approximating ColoredGraph Problems | 281 |

On the Average Sensitivity of Testing SquareFree Numbers | 291 |

Binary Enumerability of Real Numbers | 300 |

GCD of Many Integers | 310 |

Multiparty Finite Computations | 318 |

Probabilistic Local Majority Voting for the Agreement Problem on Finite Graphs | 330 |

Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs | 92 |

Layout Problems on Lattice Graphs | 103 |

A New Transference Theorem in the Geometry of Numbers | 113 |

On Covering and Rank Problems for Boolean Matrices and Their Applications | 123 |

A Combinatorial Algorithm for Pfaffians | 134 |

How to Swap a Failing Edge of a Single Source Shortest Paths Tree | 144 |

On Bounds for the kPartitioning of Graphs | 154 |

A Faster Algorithm for Computing Minimum 5Way and 6Way Cuts in Graphs | 164 |

Probabilities to Accept Languages by Quantum Finite Automata | 174 |

DistributionallyHard Languages | 184 |

Circuits and ContextFree Languages | 194 |

On the NegationLimited Circuit Complexity of Merging | 204 |

SuperPolynomial Versus HalfExponential Circuit Size in the Exponential Hierarchy | 210 |

Efficient Learning of Some Linear Matrix Languages | 221 |

Minimizing Mean Response Time in Batch Processing System | 231 |

Approximation Algorithms for Bounded Facility Location | 241 |

Scheduling Trees onto Hypercubes and Grids Is NP complete | 251 |

A DynamicProgramming Bound for the Quadratic Assignment Problem | 339 |

A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases | 349 |

On Routing in Circulant Graphs | 360 |

Minimum Congestion Embedding of Complete Binary Trees into Tori | 370 |

Maximum Stabbing Line in 2D Plane | 379 |

Generalized Shooter Location Problem | 389 |

A Competitive Online Algorithm for the Paging Problem with Shelf Memory | 400 |

Using Generalized Forecasts for Online Currency Conversion | 409 |

On SRegular PrefixRewriting Systems and Automatic Structures | 422 |

Tractable and Intractable SecondOrder Matching Problems | 432 |

Efficient FixedSize Systolic Arrays for the Modular Multiplication | 442 |

Improving Parallel Computation with Fast Integer Sorting | 452 |

A Combinatorial Approach to Performance Analysis of a SharedMemory Multiprocessor | 462 |

A Fast Approximation Algorithm for TSP with Neighborhoods and RedBlue Separation | 473 |

An Efficient Algorithm for Approximating Maximum Independent Set | 483 |

493 | |

### Other editions - View all

### Common terms and phrases

approximation algorithm automata base Berlin Heidelberg 1999 binary Boolean function circuit circuit complexity circulant graphs coloring competitive ratio complexity component Computer Science consider constant construct contains corresponding cycle deﬁne defined denote deterministic distance distribution elements embedding enumeration exists finite gate given graph G Hence hierarchical independent set input integer internal k-fat language lattice leaf Lemma length linear LNCS logn lower bound matching expression matrix matroid maximum maximum independent set memory minimal minimum minimum spanning tree nodes NP-complete NP-hard obtain operations optimal output paper partition path pclow permutation Pfaffian planar graph polynomial prefix-rewriting system Proc processing processors Proof prove random real numbers s-regular satisﬁes satisfying scheduling sequence shortest solution solved spanning tree Springer-Verlag Berlin Heidelberg step subgraph subset subtree swap systolic array Theorem transform vector vertex vertices Web graph weight