Computing and Combinatorics: Third Annual International Conference, COCOON ’97 Shanghai, China, August 20–22, 1997 Proceedings

Sajal K. Das, M. Cristina Pinotti (auth.), Tao Jiang, D. T. Lee (eds.)354063357X, 9783540633570

This book constitutes the refereed proceedings of the Third Annual International Computing and Combinatorics Conference, COCOON’97, held in Shanghai, China, in August 1997.
The volume presents 53 revised full papers selected from a total of 106 submissions. The papers are organized in sections on parallel and distributed computing, computational geometry, complexity, computational biology, computability, cryptography and computational finance, graph algorithms, algorithms, rewriting and logic, algorithms and applications, automata languages and complexity, and mathematical programming and genetic algorithms.

---

Table of contents :
Conflict-free access to templates of trees and hypercubes in parallel memory systems….Pages 1-10
Many-to-one packet routing via matchings….Pages 11-17
A multi-tree generating routing scheme using acyclic orientations….Pages 18-22
An algorithm for Heilbronn’s problem….Pages 23-31
Optimal multiresolution polygonal approximation….Pages 32-41
Constructing a strongly convex superhull of points….Pages 42-51
Fast range searching with Delaunay Triangulations….Pages 52-61
Resolution of Hartmanis’ conjecture for NL-hard sparse sets….Pages 62-71
Can large fanin circuits perform reliable computations in the presence of noise?….Pages 72-81
On set systems with restricted intersections modulo a composite number….Pages 82-90
Size and variable ordering of OBDDs representing threshold functions….Pages 91-100
The performance of neighbor-joining algorithms of phylogeny reconstruction….Pages 101-110
Inferring evolutionary trees with strong combinatorial evidence….Pages 111-123
Parsimony is hard to beat!….Pages 124-133
On the complexity of computing evolutionary trees….Pages 134-145
Computable invariance….Pages 146-155
Subclasses of computable real valued functions….Pages 156-165
Computability on continuous, lower semi-continuous and upper semi-continuous real functions….Pages 166-175
Contrast-optimal k out of n secret sharing schemes in visual cryptography….Pages 176-185
A Rabin-type scheme based on y 2 ≡ x 3 + bx 2 mod n ….Pages 186-191
Optimal bidding algorithms against cheating in multiple-object auctions….Pages 192-201
Spring algorithms and symmetry….Pages 202-211
Generalized vertex-rankings of partial k -trees….Pages 212-221
A selected tour of the theory of identification matrices….Pages 222-231
Efficient domination on permutation graphs and trapezoid graphs….Pages 232-241
On physical mapping algorithms: An error-tolerant test for the consecutive ones property….Pages 242-250
The median problem for breakpoints in comparative genomics….Pages 251-263
Fast algorithms for aligning sequences with restricted affine gap penalties….Pages 264-273
A matrix representation of phylogenetic trees….Pages 274-283
Edge and node searching problems on trees….Pages 284-293
Construction of nearly optimal multiway trees….Pages 294-303
Optimal algorithms for circle partitioning….Pages 304-310
Hexagonal routing of multiterminal nets….Pages 311-320
Design and analysis of parallel set-term unification….Pages 321-330
On modularity of completeness in order-sorted term rewriting systems….Pages 331-342
A three-valued quantificational logic of context….Pages 343-352
A compact storage scheme for fast wavelet-based subregion retrieval….Pages 353-362
A declustering algorithm for minimising spatial join cost….Pages 363-372
Fixed topology steiner trees and spanning forests with applications in network communications….Pages 373-382
A branch-and-bound algorithm for computing node weighted steiner minimum trees….Pages 383-392
A complete characterization of repetitive morphisms over the two-letter alphabet….Pages 393-402
An algorithm for identifying spliced languages….Pages 403-411
The shapes of trees….Pages 412-421
Tally languages accepted by alternating multitape finite automata….Pages 422-430
Independent spanning trees of chordal rings….Pages 431-440
Rearrangeable graphs….Pages 441-450
Projective torus networks….Pages 451-459
On the 100% rule of sensitivity analysis in linear programming….Pages 460-469
Enumerating triangulations for products of two simplices and for arbitrary configurations of points….Pages 470-481
Tree structure genetic algorithm with a nourishment mechanism….Pages 482-491
An approach to scalability of parallel matrix multiplication algorithms….Pages 492-501
Limited acceleration mechanism for cell loss free flow control in ATM networks….Pages 502-511
They are just butterflies….Pages 512-513
Mutual search….Pages 514-514
Eigenvalues, eigenvectors, and graph partitioning….Pages 515-515
Corrigendum: Exact learning of subclasses of CDNF formulas with membership queries….Pages 516-519