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

Jaroslav Nešetřil (eds.)3540662510, 9783540662518

The 7th Annual European Symposium on Algorithms (ESA ’99) is held in Prague, Czech Republic, July 16-18, 1999. This continued the tradition of the meetings which were held in – 1993 Bad Honnef (Germany) – 1994 Utrecht (Netherlands) – 1995 Corfu (Greece) – 1996 Barcelona (Spain) – 1997 Graz (Austria) – 1998 Venice (Italy) (The proceedingsof previousESA meetings were publishedas Springer LNCS v- umes 726, 855, 979, 1136, 1284, 1461.) In the short time of its history ESA (like its sister meeting SODA) has become a popular and respected meeting. The call for papers stated that the “Symposium covers research in the use, design, and analysis of ef?cient algorithms and data structures as it is carried out in c- puter science, discrete applied mathematics and mathematical programming. Papers are solicited describing original results in all areas of algorithmic research, including but not limited to: Approximation Algorithms; Combinatorial Optimization; Compu- tional Biology; Computational Geometry; Databases and Information Retrieval; Graph and Network Algorithms; Machine Learning; Number Theory and Computer Algebra; On-line Algorithms; Pattern Matching and Data Compression; Symbolic Computation.

---

Table of contents :
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