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

Front Cover
Takao Asano, Hiroshi Imai, D.T. Lee, Shin-ichi Nakano, Takeshi Tokuyama
Springer Science & Business Media, Jul 7, 1999 - Computers - 494 pages
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
Author Index
493
Copyright

Other editions - View all

Common terms and phrases