Matthew Andrews, Michel X. Goemans, Lisa Zhang (auth.), Jin-Yi Cai, Chak Kuen Wong (eds.)3540613323, 9783540613329
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.
Table of contents :
Improved bounds for on-line load balancing….Pages 1-10
O ( n log n )-average-time algorithm for shortest network under a given topology….Pages 11-20
Steiner problems on directed acyclic graphs….Pages 21-30
Wormhole versus deflection routing: A case study on the mesh….Pages 31-40
On sparse parity check matrices (extended abstract)….Pages 41-49
Finding a hidden code by asking questions….Pages 50-55
Improved length lower bounds for reflecting sequences….Pages 56-67
Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders….Pages 68-80
Output-sensitive reporting of disjoint paths (extended abstract)….Pages 81-91
Rectangular grid drawings of plane graphs….Pages 92-105
Area-efficient algorithms for upward straight-line tree drawings….Pages 106-116
Straight skeletons for general polygonal figures in the plane….Pages 117-126
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)….Pages 127-135
A note on the simulation of exponential threshold weights….Pages 136-141
Harmonic analysis, real approximation, and the communication complexity of Boolean functions….Pages 142-151
Finding large planar subgraphs and large subgraphs of a given genus….Pages 152-161
Efficient deterministic algorithms for embedding graphs on books….Pages 162-168
Optimal bi-level augmentation for selective! enhancing graph connectivity with applications….Pages 169-178
Exact learning of subclasses of CDNF formulas with membership queries….Pages 179-188
Fast separator decomposition for finite element meshes….Pages 189-198
Reduction algorithms for constructing solutions in graphs with small treewidth….Pages 199-208
Fast RNC and NC algorithms for finding a maximal set of paths with an application….Pages 209-218
Sparse suffix trees….Pages 219-230
Depth-efficient threshold circuits for multiplication and symmetric function computation….Pages 231-240
A note on the self-witnessing property of computational problems….Pages 241-249
The inverse satisfiability problem….Pages 250-259
The join can lower complexity….Pages 260-267
On the distribution of eigenvalues of graphs….Pages 268-272
On the difficulty of designing good classifiers….Pages 273-279
Approximating latin square extensions….Pages 280-289
Approximating minimum keys and optimal substructure screens….Pages 290-299
Reductions and convergence rates of average time….Pages 300-309
On the complexity of computational problems associated with simple stochastic games….Pages 310-322
On the complexity of commutativity analysis….Pages 323-332
Improved non-approximability results for vertex cover with density constraints….Pages 333-342
Some notes on the nearest neighbour interchange distance….Pages 343-351
Distributed computing in asynchronous networks with byzantine edges….Pages 352-360
Weight biased leftist trees and modified skip lists….Pages 361-370
Probabilistic analysis of local search and NP-completeness result for constraint satisfaction….Pages 371-380
On the reconfiguration of chains….Pages 381-390
Two-guarding a rectilinear polygon….Pages 391-400
Three systems for shared generation of authenticators….Pages 401-410
Efficient generation of elliptic curve cryptosystems….Pages 411-416
Superconnectivity for minimal multi-loop networks….Pages 417-419
Reviews
There are no reviews yet.