A. K. Amoura, E. Bampis, C. Kenyon, Y. Manoussakis (auth.), Rainer Burkard, Gerhard Woeginger (eds.)3540633979, 9783540633976
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.
Table of contents :
Scheduling independent multiprocessor tasks….Pages 1-12
On local search for weighted κ-set packing….Pages 13-22
On-line machine covering….Pages 23-36
Area-efficient static and incremental graph drawings….Pages 37-52
Denesting by bounded degree radicals….Pages 53-63
a linear time algorithm for the arc disjoint Menger problem in planar directed graphs….Pages 64-77
Distance approximating trees for chordal and dually chordal graphs….Pages 78-91
Decomposition of integer programs and of generating sets….Pages 92-103
Bounded degree spanning trees….Pages 104-117
Optimal adaptive broadcasting with a bounded fraction of faulty nodes….Pages 118-129
Weighted graph separators and their applications….Pages 130-143
A new exact algorithm for general orthogonal d-dimensional knapsack problems….Pages 144-156
Dynamic data structures for realtime management of large geometric scenes….Pages 157-170
Solving rectilinear Steiner tree problems exactly in theory and practice….Pages 171-185
Dynamically switching vertices in planar graphs….Pages 186-199
A new family of randomized algorithms for list accessing….Pages 200-216
On-line construction of two-dimensional suffix trees….Pages 217-231
Scheduling multiclass queueing networks on parallel servers: Approximate and heavy-traffic optimality of Klimov’s priority rule….Pages 232-245
Optimal reconstruction of graphs under the additive model….Pages 246-258
Fixing variables in semidefinite relaxations….Pages 259-270
Test sets of the knapsack problem and simultaneous diophantine approximation….Pages 271-283
Three-dimensional meshes are less powerful than two-dimensional ones in oblivious routing….Pages 284-295
Fault-tolerant real-time scheduling….Pages 296-307
Collecting garbage pages in a distributed shared memory with reduced memory and communication overhead….Pages 308-325
Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems….Pages 326-340
Minimum spanning trees in d dimensions….Pages 341-349
Relaxed balance for search trees with local rebalancing….Pages 350-363
Improved approximations for minimum cardinality quadrangulations of finite element meshes….Pages 364-377
Dynamic storage allocation with known durations….Pages 378-387
Coloring in sublinear time….Pages 388-401
Competitive analysis of on-line stack-up algorithms….Pages 402-415
Scheduling-LPs bear probabilities randomized approximations for min-sum criteria….Pages 416-429
On piercing sets of axis-parallel rectangles and rings….Pages 430-442
Seven problems: So different yet close….Pages 443-458
Linear-time reconstruction of Delaunay triangulations with applications….Pages 459-471
Approximating satisfiable satisfiability problems….Pages 472-485
Algorithms for computing signs of 2 x 2 determinants: Dynamics and average-case analysis….Pages 486-499
Reconstructing the topology of a CAD model – A discrete approach -….Pages 500-513
Reviews
There are no reviews yet.