Algorithms - ESA 2002 : 10th Annual European Symposium, Rome, Italy, September 17-21, 2002, Proceedings / edited by Rolf Möhring, Rajeev Raman.

Format:

Book

Contributor:

Möhring, Rolf, editor.

Raman, Rajeev, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Lecture notes in computer science 0302-9743 ; 2461.

Lecture Notes in Computer Science, 0302-9743 ; 2461

Language:

English

Subjects (All):

Computer programming.

Algorithms.

Computer science--Mathematics.

Computer science.

Numerical analysis.

Data structures (Computer science).

Computer graphics.

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Numeric Computing.

Data Structures.

Computer Graphics.

Local Subjects:

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Numeric Computing.

Data Structures.

Computer Graphics.

Physical Description:

1 online resource (XXVIII, 919 pages).

Edition:

First edition 2002.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2002.

System Details:

text file PDF

Summary:

This volume contains the 74 contributed papers and abstracts of 4 of the 5 invited talks presented at the 10th Annual European Symposium on Algorithms (ESA 2002), held at the University of Rome "La Sapienza", Rome, Italy, 17-21 September, 2002. For the ?rst time, ESA had two tracks, with separate program committees, which dealt respectively with: - the design and mathematical analysis of algorithms (the "Design and An- ysis" track); - real-world applications, engineering and experimental analysis of algorithms (the "Engineering and Applications" track). Previous ESAs were held in Bad Honnef, Germany (1993); Utrecht, The Neth- lands (1994); Corfu, Greece (1995); Barcelona, Spain (1996); Graz, Austria (1997); Venice, Italy (1998); Prague, Czech Republic (1999); Saarbruc ̈ ken, Ger- ? many (2000), and Arhus, Denmark (2001). The predecessor to the Engineering and Applications track of ESA was the Annual Workshop on Algorithm En- neering (WAE). Previous WAEs were held in Venice, Italy (1997), Saarbruc ̈ ken, ? Germany (1998), London, UK (1999), Saarbru ̈cken, Germany (2000), and Arhus, Denmark (2001). The proceedings of the previous ESAs were published as Springer LNCS volumes 726, 855, 979, 1284, 1461, 1643, 1879, and 2161. The proceedings of WAEs from 1999 onwards were published as Springer LNCS volumes 1668, 1982, and 2161.

Contents:

Invited Lectures

Solving Traveling Salesman Problems

Computing Shapes from Point Cloud Data

Mechanism Design for Fun and Profit

On Distance Oracles and Routing in Graphs

Contributed Papers

Kinetic Medians and kd-Trees

Range Searching in Categorical Data: Colored Range Searching on Grid

Near-Linear Time Approximation Algorithms for Curve Simplification

Translating a Planar Object to Maximize Point Containment

Approximation Algorithms for k-Line Center

New Heuristics and Lower Bounds for the Min-Max k-Chinese Postman Problem

SCIL - Symbolic Constraints in Integer Linear Programming

Implementing I/O-efficient Data Structures Using TPIE

On the k-Splittable Flow Problem

Partial Alphabetic Trees

Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router

Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy

Two Simplified Algorithms for Maintaining Order in a List

Efficient Tree Layout in a Multilevel Memory Hierarchy

A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons

TSP with Neighborhoods of Varying Size

1.375-Approximation Algorithm for Sorting by Reversals

Radio Labeling with Pre-assigned Frequencies

Branch-and-Bound Algorithms for the Test Cover Problem

Constructing Plane Spanners of Bounded Degree and Low Weight

Eager st-Ordering

Three-Dimensional Layers of Maxima

Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy

Geometric Algorithms for Density-Based Data Clustering

Balanced-Replication Algorithms for Distribution Trees

Butterflies and Peer-to-Peer Networks

Estimating Rarity and Similarity over Data Stream Windows

Efficient Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels

Frequency Estimation of Internet Packet Streams with Limited Space

Truthful and Competitive Double Auctions

Optimal Graph Exploration without Good Maps

Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

Non-independent Randomized Rounding and an Application to Digital Halftoning

Computing Homotopic Shortest Paths Efficiently

An Algorithm for Dualization in Products of Lattices and Its Applications

Determining Similarity of Conformational Polymorphs

Minimizing the Maximum Starting Time On-line

Vector Assignment Problems: A General Framework

Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice

Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique

Online Companion Caching

Deterministic Communication in Radio Networks with Large Labels

A Primal Approach to the Stable Set Problem

Wide-Sense Nonblocking WDM Cross-Connects

Efficient Implementation of a Minimal Triangulation Algorithm

Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial-Time Approximation Scheme

The Probabilistic Analysis of a Greedy Satisfiability Algorithm

Dynamic Additively Weighted Voronoi Diagrams in 2D

Time-Expanded Graphs for Flow-Dependent Transit Times

Partially-Ordered Knapsack and Applications to Scheduling

A Software Library for Elliptic Curve Cryptography

Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows

Randomized Approximation Algorithms for Query Optimization Problems on Two Processors

Covering Things with Things

On-Line Dial-a-Ride Problems under a Restricted Information Model

Approximation Algorithm for the Maximum Leaf Spanning Tree Problem for Cubic Graphs

Engineering a Lightweight Suffix Array Construction Algorithm

Complexity of Compatible Decompositions of Eulerian Graphs and Their Transformations

External-Memory Breadth-First Search with Sublinear I/O

Frequency Channel Assignment on Planar Networks

Design and Implementation of Efficient Data Types for Static Graphs

An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem

A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options

Sorting 13 Elements Requires 34 Comparisons

Extending Reduction Techniques for the Steiner Tree Problem

A Comparison of Multicast Pull Models

Online Scheduling for Sorting Buffers

Finding the Sink Takes Some Time

Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design

Minimizing Makespan and Preemption Costs on a System of Uniform Machines

Minimizing the Total Completion Time On-line on a Single Machine, Using Restarts

High-Level Filtering for Arrangements of Conic Arcs

An Approximation Scheme for Cake Division with a Linear Number of Cuts

A Simple Linear Time Algorithm for Finding Even Triangulations of 2-Connected Bipartite Plane Graphs.

Other Format:

Printed edition:

ISBN:

978-3-540-45749-7

9783540457497

Access Restriction:

Restricted for use by site license.