Algorithms - ESA '97: 5th Annual European Symposium, Graz, Austria, September 15-17, 1997. ProceedingsRainer Burkard, Gerhard Woeginger Springer Science & Business Media, 1997 M08 27 - 513 pages This book constitutes the refereed proceedings of the 5th Annual International European Symposium on Algorithms, ESA'97, held in Graz, Austria, September 1997. The 38 revised full papers presented were selected from 112 submitted papers. The papers address a broad spectrum of theoretical and applicational aspects in algorithms theory and design. Among the topics covered are approximation algorithms, graph and network algorithms, combinatorial optimization, computational biology, computational mathematics, data compression, distributed computing, evolutionary algorithms, neural computing, online algorithms, parallel computing, pattern matching, and others. |
Contents
Scheduling Independent Multiprocessor Tasks | 1 |
On Local Search for Weighted kSet Packing | 13 |
OnLine Machine Covering | 23 |
AreaEfficient Static and Incremental Graph Drawings | 37 |
Denesting by Bounded Degree Radicals | 53 |
A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs | 64 |
Distance Approximating Trees for Chordal and Dually Chordal Graphs | 78 |
Decomposition of Integer Programs and of Generating Sets | 92 |
Test Sets of the Knapsack Problem and Simultaneous Diophantine Approximation | 271 |
ThreeDimensional Meshes are Less Powerful than TwoDimensional Ones in Oblivious Routing | 284 |
FaultTolerant RealTime Scheduling | 296 |
Collecting Garbage Pages in a Distributed Shared Memory with Reduced Memory and Communication Overhead | 308 |
QuasiFully Dynamic Algorithms for TwoConnectivity Cycle Equivalence and Related Problems | 326 |
Minimum Spanning Trees in d Dimensions | 341 |
Relaxed Balance for Search Trees with Local Rebalancing | 350 |
Improved Approximations for Minimum Cardinality Quadrangulations of Finite Element Meshes | 364 |
Bounded Degree Spanning Trees | 104 |
Optimal Adaptive Broadcasting with a Bounded Fraction of Faulty Nodes | 118 |
Weighted Graph Separators and Their Applications | 130 |
A New Exact Algorithm for General Orthogonal DDimensional Knapsack Problems | 144 |
Dynamic Data Structures for Realtime Management of Large Geometric Scenes | 157 |
Solving Rectilinear Steiner Tree Problems Exactly in Theory and Practice | 171 |
Dynamically Switching Vertices in Planar Graphs | 186 |
A New Family of Randomized Algorithms for List Accessing | 200 |
OnLine Construction of TwoDimensional Suffix Trees | 217 |
Approximate and HeavyTraffic Optimality of Klimovs Priority Rule | 232 |
Optimal Reconstruction of Graphs Under the Additive Model | 246 |
Fixing Variables in Semidefinite Relaxations | 259 |
Dynamic Storage Allocation with Known Durations | 378 |
Coloring in Sublinear Time | 388 |
Competitive Analysis of online StackUp Algorithms | 402 |
SchedulingLPs Bear Probabilities Randomized Approximations for MinSum Criteria | 416 |
On Piercing Sets of AxisParallel Rectangles and Rings | 430 |
So Different yet Close | 443 |
LinearTime Reconstruction of Delaunay Triangulations with Applications | 459 |
Approximating Satisfiable Satisfiability Problems | 472 |
Dynamics and AverageCase Analysis | 486 |
Reconstructing the Topology of a CAD Model A Discrete Approach | 500 |
Common terms and phrases
apply approximation algorithms arbitrary assigned assume biconnected bins C₁ chordal graph competitive ratio Computer Science cone configuration connected consider constant constraints construction contains corresponding cost cycle d-separating data structure decomposition define deleted denesting denote dynamic algorithms edge full components fully dynamic given graph G Greedy algorithm Hilbert basis insertion integer program interval interval graph k-connected graph least Lemma Let G linear lower bound LP relaxation machine matrix mesh elements messages minimal minimum nested radical node NP-complete O(log on-line algorithm optimal pair pallet parallel partition path performance planar graph polygon polynomial problem Proc processors Proof queries randomized algorithm rebalancing operations rectangles relaxation relaxed balance satisfying scheduling semidefinite sequence solution spanning tree stack-up Steiner step storage subgraph subset suffix T-tree Theorem triangle update v₁ variables vectors vertex vertices weight