3. ESA 1995: Corfu, Greece

Key Note Address

• Shimon Even, Gene Itkis, Sergio Rajsbaum:
  On Mixed Connectivity Certificates (Extended Abstract). 1-16
  

Session 1

• Armin Bäumker, Wolfgang Dittrich, Friedhelm Meyer auf der Heide:
  Truly Efficient Parallel Algorithms: c-Optimal Multisearch for an Extension of the BSP Model (Extended Abstract). 17-30
  
• Shiva Chaudhuri, Christos D. Zaroliagis:
  Optimal Parallel Shortest Paths in Small Treewidth Digraphs. 31-45
  
• Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann:
  Shared Memory Simulations with Triple-Logarithmic Delay. 46-59
  
• Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci:
  Implementing Shared Memory on Mult-Dimensional Meshes and on the Fat-Tree (Extended Abstract). 60-74
  
• Michael Kaufmann, Jop F. Sibeyn, Torsten Suel:
  Beyond the Worst-Case Bisection Bound: Fast Sorting and Ranking on Meshes. 75-88
  
• Bogdan S. Chlebus, Leszek Gasieniec, Andrzej Pelc:
  Fast Deterministic Simulation of Computations on Faulty Parallel Machines. 89-101
  

Session 2

• Bruno Codenotti, Peter Gemmell, Janos Simon:
  Average Circuit Depth and Average Communication Complexity. 102-112
  
• Joseph Gil, Alon Itai:
  Packing Trees. 113-127
  
• Vladimir G. Deineko, Rüdiger Rudolf, Gerhard J. Woeginger:
  Sometimes Travelling is Easy: The Master Tour Problem. 128-141
  

Session 3

• Itsik Pe'er, Ron Shamir:
  Interval Graphs with Side (and Size) Constraints. 142-154
  
• Andrew V. Goldberg, Alexander V. Karzanov:
  Maximum Skew-Symmetric Flows. 155-170
  
• Monika Rauch Henzinger, Johannes A. La Poutré:
  Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs. 171-184
  
• Kurt Mehlhorn, Volker Priebe:
  On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka. 185-198
  
• Thore Husfeldt:
  Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink. 199-212
  
• Qing-Wen Feng, Robert F. Cohen, Peter Eades:
  Planarity for Clustered Graphs. 213-226
  

Session 4

• Benny Chor, Madhu Sudan:
  A Geometric Approach to Betweenness. 227-237
  
• Evanthia Papadopoulou, D. T. Lee:
  Efficient Computation of the Geodesic Voronoi Diagram of Points in a Simple Polygon (Extended Abstract). 238-251
  
• Mark de Berg:
  Linear Size Binary Space Partitions for Fat Objects. 252-263
  
• L. Paul Chew, Dorit Dor, Alon Efrat, Klara Kedem:
  Geometric Pattern Matching in d-Dimensional Space. 264-279
  
• Cao An Wang, Francis Y. L. Chin:
  Finding the Constrained Delaunay Triangulation and Constrainted Voronoi Diagram of a Simple Polygon in Linear-Time (Extended Abstract). 280-294
  

Session 5

• Lars Arge, Darren Erik Vengroff, Jeffrey Scott Vitter:
  External-Memory Algorithms for Processing Line Segments in Geographic Information Systems (Extended Abstract). 295-310
  
• Eduardo F. Barbosa, Gonzalo Navarro, Ricardo A. Baeza-Yates, Chris H. Perleberg, Nivio Ziviani:
  Optimized Binary Search and Text Retrieval. 311-326
  
• Erkki Sutinen, Jorma Tarhio:
  On Using q-Gram Locations in Approximate String Matching. 327-340
  

Session 6

• Friedhelm Meyer auf der Heide, Christian Scheideler:
  Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks. 341-354
  
• Jeffery Westbrook:
  Load Balancing for Response Time. 355-368
  
• Pascal Berthomé, Th. Duboux, Torben Hagerup, Ilan Newman, Assaf Schuster:
  Self-Simulation for the Passive Optical Star Model. 369-380
  

Session 7

• Martin Farach, Teresa M. Przytycka, Mikkel Thorup:
  Computing the Agreement of Trees with Bounded Degrees. 381-393
  
• Bo Yu, Joseph Cheriyan:
  Approximation Algorithms for Feasible Cut and Multicut Problems. 394-408
  
• Maria J. Serna, Fatos Xhafa:
  On Parallel versus Sequential Approximation. 409-419
  
• Frank Wagner, Alexander Wolff:
  An Efficient and Effective Approximation Algorithm for the Map Labeling Problem. 420-433
  
• Ton Kloks, Dieter Kratsch, Haiko Müller:
  Approximating the Bandwidth for Asteroidal Triple-Free Graphs. 434-447
  

Session 8

• Devdatt P. Dubhashi, Alessandro Panconesi:
  Near-Optimal Distributed Edge Coloring. 448-459
  
• Marshall W. Bern, David Eppstein, Leonidas J. Guibas, John Hershberger, Subhash Suri, Jan Wolter:
  The Centroid of Points with Approximate Weights. 460-472
  
• Andreas S. Schulz, Robert Weismantel, Günter M. Ziegler:
  0/1-Integer Programming: Optimization and Augmentation are Equivalent. 473-483
  
• Bala Kalyanasundaram, Kirk Pruhs:
  The Online Transportation Problem. 484-493
  
• Petra Mutzel:
  A Polyhedral Approach to Planar Augmentation and Related Problems. 494-507
  

Session 9

• Ornan Ori Gerstel, Avishai Wool, Shmuel Zaks:
  Optimal Layouts on a Chain ATM Network (Extended Abstract). 508-522
  
• Noga Alon, Zvi Galil, Moti Yung:
  Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary. 523-537
  
• Sudhanshu Aggarwal, Juan A. Garay, Amir Herzberg:
  Adaptive Video on Demand. 538-553
  

Session 10

• Patricio V. Poblete, J. Ian Munro, Thomas Papadakis:
  The Binomial Transform and its Application to the Analysis of Skip Lists. 554-569
  
• Peter Damaschke:
  An Optimal Parallel Algorithm for Digital Curve Segmentation Using Hough Polygons and Monotone Function Search. 570-581
  
• Rolf Klein, Andrzej Lingas:
  Fast Skeleton Construction. 582-595