Algorithms — ESA’ 98 [electronic resource] : 6th Annual European Symposium Venice, Italy, August 24–26, 1998 Proceedings / edited by Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, Geppino Pucci.Material type: TextLanguage: English Series: Lecture Notes in Computer Science: 1461Publisher: Berlin, Heidelberg : Springer Berlin Heidelberg, 1998Description: XII, 524 p. online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9783540685302Subject(s): Computer science | Computer Communication Networks | Data structures (Computer science) | Computer software | Electronic data processing | Computational complexity | Distribution (Probability theory) | Computer Science | Algorithm Analysis and Problem Complexity | Discrete Mathematics in Computer Science | Computer Communication Networks | Data Structures | Probability Theory and Stochastic Processes | Numeric ComputingAdditional physical formats: Printed edition:: No titleDDC classification: 005.1 LOC classification: QA76.9.A43Online resources: Click here to access online
Invited Lectures -- External Memory Algorithms -- Design and Analysis of Dynamic Processes: A Stochastic Approach (Invited Paper) -- Data Structures -- Car-Pooling as a Data Structuring Device: The Soft Heap -- Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property -- Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures -- Strings and Biology -- Augmenting Suffix Trees, with Applications -- Longest Common Subsequence from Fragments via Sparse Dynamic Programming -- Computing the Edit-Distance Between Unrooted Ordered Trees -- Analogs and Duals of the MAST Problem for Sequences and Trees -- Numerical Algorithms -- Complexity Estimates Depending on Condition and Round-Off Error -- Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting -- Fast Algorithms for Linear Algebra Modulo N -- A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers -- Geometry -- Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time -- A Robust Region Approach to the Computation of Geometric Graphs (Extended Abstract) -- Positioning Guards at Fixed Height Above a Terrain — An Optimum Inapproximability Result -- Two-Center Problems for a Convex Polygon (Extended Abstract) -- Constructing Binary Space Partitions for Orthogonal Rectangles in Practice -- Randomized and On-Line Algorithms -- A Fast Random Greedy Algorithm for the Component Commonality Problem -- Maximizing Job Completions Online -- A Randomized Algorithm for Two Servers on the Line (Extended Abstract) -- Parallel and Distributed Algorithms I -- On Nonblocking Properties of the Beneš Network -- Adaptability and the Usefulness of Hints (Extended Abstract) -- Fault-Tolerant Broadcasting in Radio Networks (Extended Abstract) -- New Bounds for Oblivious Mesh Routing -- Evaluating Server-Assisted Cache Replacement in the Web -- Graph Algorithms -- Fully Dynamic Shortest Paths and Negative Cycles Detection on Digraphs with Arbitrary Arc Weights -- A Functional Approach to External Graph Algorithms -- Minimal Triangulations for Graphs with “Few” Minimal Separators -- Finding an Optimal Path without Growing the Tree -- An Experimental Study of Dynamic Algorithms for Directed Graphs -- Matching Medical Students to Pairs of Hospitals: A New Variation on a Well-known Theme -- Parallel and Distributed Algorithms II -- ?-Stepping : A Parallel Single Source Shortest Path Algorithm -- Improved Deterministic Parallel Padded Sorting -- Analyzing an Infinite Parallel Job Allocation Process -- Nearest Neighbor Load Balancing on Graphs -- Optimization -- 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves -- Moving-Target TSP and Related Problems -- Fitting Points on the Real Line and Its Application to RH Mapping -- Approximate Coloring of Uniform Hypergraphs (Extended Abstract) -- Techniques for Scheduling with Rejection -- Computer-Aided Way to Prove Theorems in Scheduling.
th This volume contains 40 contributed papers accepted for presentation at the 6 Annual European Symposium on Algorithms (ESA’98), Venice, Italy, August 24–26, 1998, and the invited lectures by Eli Upfal (Brown) and Je?rey Vitter (Duke). ESA is an annual meeting, with previous meetings held in Bad Honnef, Utrecht, Corfu, Barcelona, and Graz, and covers research in the use, design, and analysis of e?cient algorithms and data structures as it is carried out in computerscience,discreteappliedmathematicsandmathematicalprogramming. Proceedings of ESA have been traditionally part of the LNCS series of Springer- Verlag. The symposium is promoted and coordinated by a steering committee, whose current composition is: Gianfranco Bilardi, Padua & UIC Kurt Mehlhorn, Saarbrucken ¨ Josep Diaz, Barcelona Ralf H. M¨ ohring, Berlin Giuseppe F. Italiano, Venice Gerhard Woeginger, Graz The Program Committee of ESA’98 consisted of: Gianfranco Bilardi, Co-chair, Kurt Mehlhorn, Saarbrucken ¨ Padua & UIC Friedhelm Meyer auf der Heide, Jean Daniel Boissonnat, Paderborn Sophia Antipolis Grammati Pantziou, Patras Kieran T. Herley, Cork Mike Paterson, Warwick Dorit Hochbaum, Berkeley Jos´ e Rolim, Geneva Giuseppe F. Italiano, Co-Chair, Erik M. Schmidt, Aarhus Venice Maria Serna, Barcelona Lud? ek Ku? cera, Prague Paul Vitanyi, Amsterdam Richard J. Lipton, Princeton Gerhard Woeginger, Graz Yishay Mansour, Tel-Aviv There were 131 extended abstracts submitted in response to a call for - pers.