4. ESA 1996: Barcelona, Spain

Session 1

• Robert Sedgewick:
  Analysis of Shellsort and Related Algorithms. 1-11
  
• Ashim Garg, Roberto Tamassia, Paola Vocca:
  Drawing with Colors (Extended Abstract). 12-26
  

Session 2

• Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc:
  Approximating the Unsatisfiability Threshold of Random Formulas (Extended Abstract). 27-38
  
• Uwe Schwiegelshohn:
  Preemptive Weighted Completion Time Scheduling of Parallel Jobs. 39-51
  
• Jordan Gergov:
  Approximation Algorithms for Dynamic Storage Allocations. 52-61
  
• Luca Trevisan:
  Positive Linear Programming, Parallel Approximation and PCP's. 62-75
  
• Rolf H. Möhring, Markus W. Schäffter, Andreas S. Schulz:
  Scheduling Jobs with Communication Delays: Using Infeasible Solutions for Approximation (Extended Abstract). 76-90
  

Session 3

• Salvador Roura, Conrado Martínez:
  Randomization of Search Trees by Subtree Size. 91-106
  
• Paolo Ferragina, S. Muthukrishnan:
  Efficient Dynamic Method-Lookup for Object Oriented Languages (Extended Abstract). 107-120
  
• Rajeev Raman:
  Priority Queues: Small, Monotone and Trans-dichotomous. 121-137
  

Session 4

• Andreas Nolte, Rainer Schrader:
  Simulated Annealing and Its Problems to Color Graphs. 138-151
  
• Samir Khuller, Yoram J. Sussmann:
  The Capacitated K-Center Problem (Extended Abstract). 152-166
  
• Toshihiro Fujito:
  A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract). 167-178
  
• Sudipto Guha, Samir Khuller:
  Approximation Algorithms for Connected Dominating Sets. 179-193
  

Session 5

• Alan M. Frieze, Wojciech Szpankowski:
  Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal. 194-207
  
• Tatsuie Tsukiji, Fatos Xhafa:
  On the Depth of Randomly Generated Circuits. 208-220
  
• Alfredo Viola, Patricio V. Poblete:
  The Analysis of Linear Probing Hashing with Buckets (Extended Abstract). 221-233
  

Session 6

• Danny Z. Chen, Wei Chen, Koichi Wada, Kimio Kawaguchi:
  Parallel Algorithms for Partitioning Sorted Sets and Related Problems. 234-245
  
• Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski, Krzysztof Lorys:
  Fast Generation of Random Permutations via Networks Simulation. 246-260
  
• Paolo Ferragina, Fabrizio Luccio:
  On the Parallel Dynamic Dictionary Matching Problem: New Results with Applications. 261-275
  
• Hans L. Bodlaender, Babette de Fluiter:
  Parallel Algorithms for Series Parallel Graphs. 277-289
  
• Mauro Leoncini, Giovanni Manzini, Luciano Margara:
  Parallel Complexity of Householder QR Factorization. 290-301
  

Session 7

• Julien Basch, Leonidas J. Guibas, G. D. Ramkumar:
  Reporting Red-Blue Intersections between Two Sets of Connected Line Segments. 302-319
  
• Helmut Alt, Ulrich Fuchs, Günter Rote, Gerald Weber:
  Matching Convex Shapes with Respect to the Symmetric Difference. 320-333
  
• Esther M. Arkin, Yi-Jen Chiang, Martin Held, Joseph S. B. Mitchell, Vera Sacristan, Steven Skiena, Tae-Heng Yang:
  On Minimum-Area Hulls (Extended Abstract). 334-348
  

Session 8

• Boris V. Cherkassky, Andrew V. Goldberg:
  Negative-Cycle Detection Algorithms. 349-363
  
• Bruce W. Watson:
  A New Regular Grammar Pattern Matching Algorithm. 364-377
  
• Juha Kärkkäinen, Erkki Sutinen:
  Lempel-Ziv Index for q-Grams. 378-391
  
• Ralf Heckmann, Thomas Lengauer:
  Computing Upper and Lower Bounds on Textile Nesting Problems. 392-405
  

Session 9

• Noga Alon, János Csirik, Sergey V. Sevastianov, Arjen P. A. Vestjens, Gerhard J. Woeginger:
  On-line and Off-line Approximation Algorithms for Vector Covering Problems. 406-418
  
• Dimitris Achlioptas, Marek Chrobak, John Noga:
  Competive Analysis of Randomized Paging Algorithms. 419-430
  
• Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Rosén:
  On-line Competive Algorithms for Call Admission in Optical Networks. 431-444
  

Session 10

• Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer:
  Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). 445-459
  
• Christos Kaklamanis, Giuseppe Persiano:
  Efficient Wavelength Routing on Directed Fiber Trees. 460-470
  
• Ishai Ben-Aroya, Donald D. Chinn, Assaf Schuster:
  A Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms. 471-485
  
• George Christopher, Martin Farach, Michael A. Trick:
  The Structure of Circular Decomposable Metrics. 486-500
  
• Anders Dessmark, Andrzej Lingas, Andrzej Proskurowski:
  Faster Algorithms for Subgraph Isomorphism of k-Connected Partial k-Trees. 501-513
  

Session 11

• Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, Christos D. Zaroliagis:
  Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane. 514-528
  
• Vincenzo Auletta, Domenico Parente, Giuseppe Persiano:
  A New Approach to Optimal Planning of Robot Motion on a Tree with Obstacles. 529-545
  
• Alejandro López-Ortiz, Sven Schuierer:
  Generalized Streets Revisited. 546-558
  

Session 12

• Christos H. Papadimitriou:
  Computational Aspacts of Organization Theory (Extended Abstract). 559-564