Algorithms - ESA '96, Vol. 113 Book

	Invited Talk: Analysis of Shellsort and Related Algorithms	1
	Drawing with Colors	12
	Approximating the Unsatisfiability Threshold of Random Formulas	27
	Preemptive Weighted Completion Time Scheduling of Parallel Jobs	39
	Approximation Algorithms for Dynamic Storage Allocation	52
	Positive Linear Programming, Parallel Approximation and PCP's	62
	Scheduling Jobs with Communication Delays: Using Infeasible Solutions for Approximation	76
	Randomization of Search Trees by Subtree Size	91
	Efficient Dynamic Method-Lookup in Object Oriented Languages	107
	Priority Queues: Small, Monotone and Trans-dichotomous	121
	Simulated Annealing and Its Problems to Color Graphs	138
	The Capacitated k-Center Problem	152
	A Unified Local Ratio Approximation of Node-Deletion Problem	167
	Approximation Algorithms for Connected Dominating Sets	179
	Greedy Algorithms for the Shortest Common Superstring that Are Asymptotically Optimal	194
	On the Depth of Randomly Generated Circuits	208
	The Analysis of Linear Probing Hashing with Buckets	221
	Parallel Algorithms for Partitioning Sorted Sets and Related Problems	234
	Fast Generation of Random Permutations via Networks Simulation	246
	On the Parallel Dynamic Dictionary Matching Problem: New Results with Application	261
	Parallel Algorithms for Series Parallel Graphs	277
	Parallel Complexity of Householder QR Factorization	290
	Reporting Red-Blue Intersections Between Two Sets of Connected Line Segments	302
	Matching Convex Shapes with Respect to the Symmetric Difference	320
	On Minimum-Area Hulls	334
	Negative Cycle Detection Algorithms	349
	A New Regular Grammar Pattern Matching Algorithm	364
	Lempel-Ziv Index for q-Grams	378
	Computing Upper and Lower Bounds on Textile Nesting Problems	392
	On-Line and Off-Line Algorithms for Vector Covering	406
	Competitive Analysis of Randomized Paging Algorithms	419
	On-Line Competitive Algorithms for Call Admission in Optical Networks	431
	Race-Condition Detection in Parallel Computation with Semaphores	445
	Efficient Wavelength Routing on Directed Fiber Trees	460
	A Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms	471
	The Structure of Circular Decomposable Metrics	486
	Faster Algorithms for Subgraph Isomorphism of k-Connected Partial k-Trees	501
	Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane	514
	A New Approach to Optimal Planning of Robot Motion on a Tree with Obstacles	529
	Generalized Streets Revisited	546
	Invited Talk: Computational Aspects of Organization Theory	559
	Author Index	565