Algorithms - ESA’ 99: 7th Annual European Symposium Prague, Czech Republic, July 16–18, 1999 Proceedings

ESA’99 Program....Pages 1-3
Adaptively-Secure Distributed Public-Key Systems....Pages 4-27
How Long Does a Bit Live in a Computer?....Pages 28-28
Approximation Algorithms for the Traveling Purchaser Problem and Its Variants in Network Design....Pages 29-40
The Impact of Knowledge on Broadcasting Time in Radio Networks....Pages 41-52
Multipacket Routing on 2-D Meshes and Its Application to Fault-Tolerant Routing....Pages 53-64
IP Address LookupMade Fast and Simple....Pages 65-76
On-Line Load Balancing in a Hierarchical Server Topology....Pages 77-88
Provably Good and Practical Strategies for Non-uniform Data Management in Networks....Pages 89-100
Approximation Algorithms for Restoration Capacity Planning....Pages 101-115
Efficient Algorithms for Integer Programs with Two Variables per Constraint....Pages 116-126
Convex Quadratic Programming Relaxations for Network Scheduling Problems....Pages 127-138
Resource-Constrained Project Scheduling:Computing Lower Bounds by Solving Minimum Cut Problems....Pages 139-150
Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines....Pages 151-162
Off-Line Temporary Tasks Assignment....Pages 163-171
Load Balancing Using Bisectors — A Tight Average-Case Analysis....Pages 172-183
On the Analysis of Evolutionary Algorithms — A Proof That Crossover Really Can Help....Pages 184-193
Motif Statistics....Pages 194-211
Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices (Extended Abstract)....Pages 212-223
On Constructing Suffix Arrays in External Memory....Pages 224-235
Strategies for Searching with Different Access Costs....Pages 236-247
On the Informational Asymmetry between Upper and Lower Bounds for Ultrametric Evolutionary Trees....Pages 248-256
Optimal Binary Search with Two Unreliable Tests and Minimum Adaptiveness....Pages 257-266
Improving Mergesort for Linked Lists....Pages 267-276
Efficient Algorithms for On-Line Symbol Ranking Compression....Pages 277-288
On List Update and Work Function Algorithms....Pages 289-300
The 3-Server Problem in the Plane....Pages 301-312
Quartet Cleaning: Improved Algorithms and Simulations....Pages 313-324
Fast and Robust Smallest Enclosing Balls....Pages 325-338
Efficient Searching for Multi—dimensional Data Made Simple....Pages 339-353
Geometric Searching over the Rationals....Pages 354-365
On Computing the Diameter of a Point Set in High Dimensional Euclidean Space....Pages 366-377
A Nearly Linear-Time Approximation Scheme for the Euclidean k -median Problem....Pages 378-389
Sum Multi-coloring of Graphs....Pages 390-401
Efficient Approximation Algorithms for the Achromatic Number....Pages 402-413
Augmenting a( k —1)-Vertex-ConnectedMultigraph to an ℓ -Edge-Connected and k -Vertex-Connected Multigraph....Pages 414-425
An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling....Pages 426-437
A Decomposition Theorem for MaximumWeight Bipartite Matchings with Applications to Evolutionary Trees....Pages 438-449
Faster Exact Solutions for Some NP-Hard Problems....Pages 450-461
A Polyhedral Algorithm for Packings and Designs....Pages 462-475
Threshold Phenomena in Random Lattices and Efficient Reduction Algorithms....Pages 476-489
On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs....Pages 490-497
Dilworth’s Theorem and Its Application for Path Systems of a Cycle—Implementation and Analysis....Pages 498-509
On 2-Coverings and 2-Packings of Laminar Families....Pages 510-520
Random Cayley Graphs with O(log|G|) Generators Are Expanders....Pages 521-526
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs....Pages 527-539
A Fast General Methodology for Information—Theoretically Optimal Encodings of Graphs....Pages 540-549