Computing and Combinatorics: Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996. Proceedings, Volume 2This 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. |
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 |
Common terms and phrases
2-block A-code algorithm approximation assignment average binary bipartite Boolean function columns complexity component Computer Science consider constant construction convex cut vertex data structure defined denote facial triangles finite formulas given graph G grid drawing H₁ IEEE input integer iteration Lemma length Let G linear log₂ lower bound matroid maximum membership queries mesh node NP-complete NP-hard number of edges O(log O(n log log obtain pair partition path planar graph plane polygon polynomial polynomial-time problem Proc processors Proof prove PSPACE random reassignment costs reduction result S₁ satisfies SBIBLK(G self-witnessing skip lists solution solve stochastic games straight skeleton subgraph subset subtree suffix tree T₁ Theorem threshold circuits triconnected Turing machine Tutte polynomial universal optimal strategies upper bound variables VERTEX COVER VERTEX COVER problem vertices Voronoi diagram wavefront wormhole routing