Algorithms — ESA '96: Fourth Annual European Symposium Barcelona, Spain, September 25–27, 1996 Proceedings

Analysis of Shellsort and related algorithms....Pages 1-11
Drawing with colors....Pages 12-26
Approximating the unsatisfiability threshold of random formulas (Extended Abstract)....Pages 27-38
Preemptive weighted completion time scheduling of parallel jobs....Pages 39-51
Approximation algorithms for dynamic storage allocation....Pages 52-61
Positive linear programming, parallel approximation and PCP\'s....Pages 62-75
Scheduling jobs with communication delays: Using infeasible solutions for approximation....Pages 76-90
Randomization of search trees by subtree size....Pages 91-106
Efficient dynamic method-lookup for object oriented languages....Pages 107-120
Priority queues: Small, monotone and trans-dichotomous....Pages 121-137
Simulated Annealing and its problems to color graphs....Pages 138-151
The capacitated K-center problem....Pages 152-166
A unified local ratio approximation of node-deletion problems....Pages 167-178
Approximation algorithms for connected dominating sets....Pages 179-193
Greedy algorithms for the shortest common superstring that are asymtotically optimal....Pages 194-207
On the depth of randomly generated circuits....Pages 208-220
The analysis of linear probing hashing with buckets....Pages 221-233
Parallel algorithms for partitioning sorted sets and related problems....Pages 234-245
Fast generation of random permutations via networks simulation....Pages 246-260
On the Parallel Dynamic Dictionary Matching problem: New results with applications....Pages 261-275
Parallel algorithms for series parallel graphs....Pages 277-289
Parallel complexity of householder QR factorization....Pages 290-301
Reporting red-blue intersections between two sets of connected line segments....Pages 302-319
Matching convex shapes with respect to the symmetric difference....Pages 320-333
On minimum-area hulls....Pages 334-348
Negative-cycle detection algorithms....Pages 349-363
A new regular grammar pattern matching algorithm....Pages 364-377
Lempel-Ziv index for q -grams....Pages 378-391
Computing upper and lower bounds on textile nesting problems....Pages 392-405
On-line and off-line approximation algorithms for vector covering problems....Pages 406-418
Competitive analysis of randomized paging algorithms....Pages 419-430
On-line competitive algorithms for call admission in optical networks....Pages 431-444
Race-condition detection in parallel computation with semaphores (extended abstract)....Pages 445-459
Efficient wavelength routing on directed fiber trees....Pages 460-470
A lower bound for nearly minimal adaptive and hot potato algorithms....Pages 471-485
The structure of circular decomposable metrics....Pages 486-500
Faster algorithms for subgraph isomorphism of κ-connected partial κ-trees....Pages 501-513
Planar spanners and approximate shortest path queries among obstacles in the plane....Pages 514-528
A new approach to optimal planning of robot motion on a tree with obstacles....Pages 529-545
Generalized streets revisited....Pages 546-558
Computational aspects of organization theory....Pages 559-564