Robert Sedgewick (auth.), Josep Diaz, Maria Serna (eds.)3540616802, 9783540616801
The book presents 40 revised full papers selected from 124 submissions; also are included extended abstracts of two invited presentations. The papers included cover all research areas on algorithms and their analysis as it is carried out in the fields of computer science, discrete applied and algorithmic mathematics, operations research, and all other areas of algorithms-oriented research, design and analysis.
Table of contents :
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
Reviews
There are no reviews yet.