Computing and Combinatorics: Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996. Proceedings, Volume 2

Front Cover
Springer Science & Business Media, Jun 5, 1996 - Computers - 419 pages
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.
 

What people are saying - Write a review

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

Contents

Improved Bounds for Online Load Balancing
1
On log nAverageTime Algorithm for Shortest Network under a Given Topology
11
Steiner Problems on Directed Acyclic Graphs
21
A Case Study on the Mesh
31
On Sparse Parity Check Matrices
41
Finding a Hidden Code by Asking Questions
50
Improved Length Lower Bounds for Reflecting Sequences
56
Combinatorial and Geometric Approaches to Counting Problems on Linear Matroids Graphic Arrangements and Partial Orders
68
DepthEfficient Threshold Circuits for Multiplication and Symmetric Function Computation
231
A Note on the SelfWitnessing Property of Computational Problems
241
The Inverse Satisfiability Problem
250
The Join Can Lower Complexity
260
On the Distribution of Eigenvalues of Graphs
268
On the Difficulty of Designing Good Classifiers
273
Approximating Latin Square Extensions
280
Approximating Minimum Keys and Optimal Substructure Screens
290

OutputSensitive Reporting of Disjoint Paths
81
Rectangular Grid Drawings of Plane Graphs
92
AreaEfficient Algorithms for Upward StraightLine Tree Drawings
106
Straight Skeletons for General Polygonal Figures in the Plane
117
A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy
127
A Note on the Simulation of Exponential Threshold Weights
136
Harmonic Analysis Real Approximation and the Communication Complexity of Boolean Functions
142
Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus
152
Efficient Deterministic Algorithms for Embedding Graphs on Books
162
Optimal BiLevel Augmentation for Selectively Enhancing Graph Connectivity with Applications
169
Exact Learning of Subclasses of CDNF Formulas with Membership Queries
179
Fast Separator Decomposition for Finite Element Meshes
189
Reduction Algorithms for Constructing Solutions in Graphs with Small Treewidth
199
Fast RNC and NC Algorithms for Finding a Maximal Set of Paths with an Application
209
Sparse Suffix Trees
219
Reductions and Convergence Rates of Average Time
300
On the Complexity of Computational Problems Associated with Simple Stochastic Games
310
On the Complexity of Commutativity Analysis
323
Improved Nonapproximability Results for Vertex Cover with Density Constraints
333
Some Notes on the Nearest Neighbour Interchange Distance
343
Distributed Computing in Asynchronous Networks with Byzantine Edges
352
Weight Biased Leftist Trees and Modified Skip Lists
361
Probabilistic Analysis of Local Search and NPCompleteness Result for Constraint Satisfaction
371
On the Reconfiguration of Chains
381
TwoGuarding a Rectilinear Polygon
391
Three Systems for Shared Generation of Authenticators
401
Efficient Generation of Elliptic Curve Cryptosystems
411
Superconnectivity for Minimal Multiloop Networks
417
Author Index
Copyright

Common terms and phrases

Bibliographic information