Algorithms - ESA '97

Scheduling independent multiprocessor tasks.- On local search for weighted ?-set packing.- On-line machine covering.- Area-efficient static and incremental graph drawings.- Denesting by bounded degree radicals.- a linear time algorithm for the arc disjoint Menger problem in planar directed graphs.- Distance approximating trees for chordal and dually chordal graphs.- Decomposition of integer programs and of generating sets.- Bounded degree spanning trees.- Optimal adaptive broadcasting with a bounded fraction of faulty nodes.- Weighted graph separators and their applications.- A new exact algorithm for general orthogonal d-dimensional knapsack problems.- Dynamic data structures for realtime management of large geometric scenes.- Solving rectilinear Steiner tree problems exactly in theory and practice.- Dynamically switching vertices in planar graphs.- A new family of randomized algorithms for list accessing.- On-line construction of two-dimensional suffix trees.- Scheduling multiclass queueing networks on parallel servers: Approximate and heavy-traffic optimality of Klimov's priority rule.- Optimal reconstruction of graphs under the additive model.- Fixing variables in semidefinite relaxations.- Test sets of the knapsack problem and simultaneous diophantine approximation.- Three-dimensional meshes are less powerful than two-dimensional ones in oblivious routing.- Fault-tolerant real-time scheduling.- Collecting garbage pages in a distributed shared memory with reduced memory and communication overhead.- Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems.- Minimum spanning trees in d dimensions.- Relaxed balance for search trees with local rebalancing.- Improved approximations for minimum cardinality quadrangulations of finite element meshes.- Dynamic storage allocation with known durations.- Coloring in sublinear time.- Competitive analysis of on-line stack-up algorithms.- Scheduling-LPs bear probabilities randomized