Computing and Combinatorics

This book constitutes the proceedings of the Second Annual International Conference on Computing and Combinatorics, COCOON '96, held in June 1996 in Hong Kong.
The 44 papers presented in the book in revised version were carefully selected from a total of 82 submissions. They describe state-of-the-art research results from various areas of theoretical computer science, combinatorics related to computing, and experimental analysis of algorithms; computational graph theory, computational geometry, and networking issues are particularly well-presented.

Inhalt
Improved bounds for on-line load balancing.- O(n log n)-average-time algorithm for shortest network under a given topology.- Steiner problems on directed acyclic graphs.- Wormhole versus deflection routing: A case study on the mesh.- On sparse parity check matrices (extended abstract).- Finding a hidden code by asking questions.- Improved length lower bounds for reflecting sequences.- Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders.- Output-sensitive reporting of disjoint paths (extended abstract).- Rectangular grid drawings of plane graphs.- Area-efficient algorithms for upward straight-line tree drawings.- Straight skeletons for general polygonal figures in the plane.- A note on uniform circuit lower bounds for the counting hierarchy (extended abstract).- A note on the simulation of exponential threshold weights.- Harmonic analysis, real approximation, and the communication complexity of Boolean functions.- Finding large planar subgraphs and large subgraphs of a given genus.- Efficient deterministic algorithms for embedding graphs on books.- Optimal bi-level augmentation for selective! enhancing graph connectivity with applications.- Exact learning of subclasses of CDNF formulas with membership queries.- Fast separator decomposition for finite element meshes.- Reduction algorithms for constructing solutions in graphs with small treewidth.- Fast RNC and NC algorithms for finding a maximal set of paths with an application.- Sparse suffix trees.- Depth-efficient threshold circuits for multiplication and symmetric function computation.- A note on the self-witnessing property of computational problems.- The inverse satisfiability problem.- The join can lower complexity.- On the distribution of eigenvalues of graphs.- On the difficulty of designing good classifiers.- Approximating latin square extensions.- Approximating minimum keys and optimal substructure screens.- Reductions and convergence rates of average time.- On the complexity of computational problems associated with simple stochastic games.- On the complexity of commutativity analysis.- Improved non-approximability results for vertex cover with density constraints.- Some notes on the nearest neighbour interchange distance.- Distributed computing in asynchronous networks with byzantine edges.- Weight biased leftist trees and modified skip lists.- Probabilistic analysis of local search and NP-completeness result for constraint satisfaction.- On the reconfiguration of chains.- Two-guarding a rectilinear polygon.- Three systems for shared generation of authenticators.- Efficient generation of elliptic curve cryptosystems.- Superconnectivity for minimal multi-loop networks.