Algorithms - ESA '96

Analysis of Shellsort and related algorithms.- Drawing with colors.- Approximating the unsatisfiability threshold of random formulas (Extended Abstract).- Preemptive weighted completion time scheduling of parallel jobs.- Approximation algorithms for dynamic storage allocation.- Positive linear programming, parallel approximation and PCP's.- Scheduling jobs with communication delays: Using infeasible solutions for approximation.- Randomization of search trees by subtree size.- Efficient dynamic method-lookup for object oriented languages.- Priority queues: Small, monotone and trans-dichotomous.- Simulated Annealing and its problems to color graphs.- The capacitated K-center problem.- A unified local ratio approximation of node-deletion problems.- Approximation algorithms for connected dominating sets.- Greedy algorithms for the shortest common superstring that are asymtotically optimal.- On the depth of randomly generated circuits.- The analysis of linear probing hashing with buckets.- Parallel algorithms for partitioning sorted sets and related problems.- Fast generation of random permutations via networks simulation.- On the Parallel Dynamic Dictionary Matching problem: New results with applications.- Parallel algorithms for series parallel graphs.- Parallel complexity of householder QR factorization.- Reporting red-blue intersections between two sets of connected line segments.- Matching convex shapes with respect to the symmetric difference.- On minimum-area hulls.- Negative-cycle detection algorithms.- A new regular grammar pattern matching algorithm.- Lempel-Ziv index for q-grams.- Computing upper and lower bounds on textile nesting problems.- On-line and off-line approximation algorithms for vector covering problems.- Competitive analysis of randomized paging algorithms.- On-line competitive algorithms for call admission in optical networks.- Race-condition detection in parallel computation with semaphores (extended abstract).- Efficient wavelength routing on directed fiber trees.- A lower bound for nearly minimal adaptive and hot potato algorithms.- The structure of circular decomposable metrics.- Faster algorithms for subgraph isomorphism of ?-connected partial ?-trees.- Planar spanners and approximate shortest path queries among obstacles in the plane.- A new approach to optimal planning of robot motion on a tree with obstacles.- Generalized streets revisited.- Computational aspects of organization theory.