Front matter
1-3
ESA’99 Program
695
Adaptively-Secure Distributed Public-Key Systems
Yair Frankel, Philip MacKenzie and Moti Yung
695
How Long Does a Bit Live in a Computer?
Bernhard Korte
696
Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design
R. Ravi and F. S. Salman
696
The Impact of Knowledge on Broadcasting Time in Radio Networks
(Extended Abstract)
Krzysztof Diks, Evangelos Kranakis, Danny Krizanc and Andrzej Pelc
695
Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing
Kazuo Iwama and Eiji Miyano
694
IP Address LookupMade Fast and Simple
Pierluigi Crescenzi, Leandro Dardini and Roberto Grossi
698
On-Line Load Balancing in a Hierarchical Server Topology
Amotz Bar-Noy, Ari Freund and Joseph (Seffi) Naor
697-698
Provably Good and Practical Strategies for Non-uniform Data Management in Networks
Friedhelm Meyer auf der Heide, Berthold Vöcking and Matthias Westermann
693
Approximation Algorithms for Restoration Capacity Planning
Steven J. Phillips and Jeffery R. Westbrook
696
Efficient Algorithms for Integer Programs with Two Variables per Constraint
(Extended Abstract)
Reuven Bar-Yehuda and Dror Rawitz
699
Convex Quadratic Programming Relaxations for Network Scheduling Problems
Martin Skutella
697
Resource-Constrained Project Scheduling:Computing Lower Bounds by Solving Minimum Cut Problems
Rolf H. Möhring, Andreas S. Schulz, Frederik Stork and Marc Uetz
693
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines
Leah Epstein and Jiří Sgall
694
Off-Line Temporary Tasks Assignment
Yossi Azar and Oded Regev
696
Load Balancing Using Bisectors — A Tight Average-Case Analysis
Stefan Bischof, Thomas Schickinger and Angelika Steger
700
On the Analysis of Evolutionary Algorithms — A Proof That Crossover Really Can Help
Thomas Jansen and Ingo Wegener
697
Motif Statistics
Abstract
Pierre Nicodème, Bruno Salvy and Philippe Flajolet
72
Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices (Extended Abstract)
Volker Heun
695
On Constructing Suffix Arrays in External Memory
Andreas Crauser and Paolo Ferragina
696
Strategies for Searching with Different Access Costs
Eduardo Sany Laber, Ruy Luiz Milidiú and Artur Alves Pessoa
72
On the Informational Asymmetry between Upper and Lower Bounds for Ultrametric Evolutionary Trees
Ting Chen and Ming-Yang Kao
698
Optimal Binary Search with Two Unreliable Tests and Minimum Adaptiveness
Ferdinando Cicalese and Daniele Mundici
694
Improving Mergesort for Linked Lists
Salvador Roura
694
Efficient Algorithms for On-Line Symbol Ranking Compression
(Extended Abstract)
Giovanni Manzini
699
On List Update and Work Function Algorithms
Eric J. Anderson, Kris Hildrum, Anna R. Karlin, April Rasala and Michael Saks
699
The 3-Server Problem in the Plane
(Extended Abstract)
Wolfgang W. Bein, Marek Chrobak and Lawrence L. Larmore
695
Quartet Cleaning: Improved Algorithms and Simulations
Vincent Berry, Tao Jiang, Paul Kearney, Ming Li and Todd Wareham
693
Fast and Robust Smallest Enclosing Balls
Bernd Gärtner
696
Efficient Searching for Multi—dimensional Data Made Simple
(Extended Abstract)
Enrico Nardelli, Maurizio Talamo and Paola Vocca
698
Geometric Searching over the Rationals
Bernard Chazelle
694
On Computing the Diameter of a Point Set in High Dimensional Euclidean Space
Daniele V. Finocchiaro and Marco Pellegrini
698-699
A Nearly Linear-Time Approximation Scheme for the Euclidean
k
-median Problem
Stavros G. Kolliopoulos and Satish Rao
693
Sum Multi-coloring of Graphs
Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman and Hadas Shanhnai
700
Efficient Approximation Algorithms for the Achromatic Number
Piotr Krysta and Krzysztof Loryś
695
Augmenting a(
k
—1)-Vertex-ConnectedMultigraph to an
ℓ
-Edge-Connected and
k
-Vertex-Connected Multigraph
Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki
696
An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling
Bram Verweij and Karen Aardal
694
A Decomposition Theorem for MaximumWeight Bipartite Matchings with Applications to Evolutionary Trees
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung and Hing-Fung Ting
696
Faster Exact Solutions for Some NP-Hard Problems
(Extended Abstract)
Limor Drori and David Peleg
697
A Polyhedral Algorithm for Packings and Designs
Lucia Moura
698
Threshold Phenomena in Random Lattices and Efficient Reduction Algorithms
Ali Akhavi
697
On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs
Alexander A. Ageev
693
Dilworth’s Theorem and Its Application for Path Systems of a Cycle—Implementation and Analysis
András A. Benczúr, Jörg Förster and Zoltán Király
72
On 2-Coverings and 2-Packings of Laminar Families
Joseph Cheriyan, Tibor Jordán and R. Ravi
698
Random Cayley Graphs with O(log|G|) Generators Are Expanders
Igor Pak
699
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
Pavol Hell, Ron Shamir and Roded Sharan
697
A Fast General Methodology for Information—Theoretically Optimal Encodings of Graphs
Xin He, Ming-Yang Kao and Hsueh-I Lu
Back matter