Andrew V. Goldberg (auth.), Jan van Leeuwen (eds.)354058434X, 9783540584346, 038758434X
The 42 papers presented were selected from a total of 159 submissions and reflect many of the current directions in algorithm research. The volume is organized into chapters on automatic graph drawing and rendering, spanners and Steiner trees, efficient data structures and complexity analysis, graph algorithms, distributed algorithms, computational geometry and its applications, operations research and combinatorial optimization, parallel computation and interconnection networks, complexity theory, and text processing
Table of contents :
Optimization algorithms for large networks….Pages 1-9
Wanna buy an algorithm? Cheap! or: Algorithms for text searching which could have commercial value….Pages 10-11
Planar drawings and angular resolution: Algorithms and bounds….Pages 12-23
A better heuristic for orthogonal graph drawings….Pages 24-35
Hamiltonian triangulations for fast rendering….Pages 36-47
Efficient construction of a bounded degree spanner with low weight….Pages 48-59
Approaching the 5/4 — approximation for rectilinear Steiner trees….Pages 60-71
Membership in constant time and minimum space….Pages 72-81
Faster searching in tries and quadtrees—An analysis of level compression….Pages 82-93
The analysis of a hashing scheme by the diagonal poisson transform….Pages 94-105
Some lower bounds for comparison-based algorithms….Pages 106-117
An efficient algorithm for edge-ranking trees….Pages 118-129
Edge-disjoint ( s, t )-paths in undirected planar graphs in linear time….Pages 130-140
A simple min cut algorithm….Pages 141-147
Approximation algorithm on multi-way maxcut partitioning….Pages 148-158
A linear-time algorithm for finding a central vertex of a chordal graph….Pages 159-170
The time complexity of updating snapshot memories….Pages 171-182
Non-exploratory self-stabilization for constant-space symmetry-breaking….Pages 183-201
On-line distributed data management….Pages 202-214
A unified scheme for detecting fundamental curves in binary edge images….Pages 215-226
How to compute the Voronoi diagram of line segments: Theoretical and experimental results….Pages 227-239
Range searching and point location among fat objects….Pages 240-253
Convex tours of bounded curvature….Pages 254-265
Optimal shortest path and minimum-link path queries in the presence of obstacles….Pages 266-277
Fast algorithms for collision and proximity problems involving moving geometric objects….Pages 278-289
Reverse-Fit: A 2-optimal algorithm for packing rectangles….Pages 290-299
An optimal algorithm for preemptive on-line scheduling….Pages 300-306
Tight approximations for resource constrained scheduling problems….Pages 307-318
An algorithm for 0–1 programming with application to airline crew scheduling….Pages 319-330
An o(n) work EREW parallel algorithm for updating MST….Pages 331-342
On the structure of DFS -forests on directed graphs and the dynamic maintenance of DFS on DAG’s….Pages 343-353
Finding and counting given length cycles….Pages 354-364
Greedy hot-potato routing on the mesh….Pages 365-376
Desnakification of mesh sorting algorithms….Pages 377-390
Tight bounds on deterministic PRAM emulations with constant redundancy….Pages 391-400
PRAM computations resilient to memory faults….Pages 401-412
An area lower bound for a class of fat-trees….Pages 413-423
A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs….Pages 424-435
The parallel complexity of eden growth, solid-on-solid growth and ballistic deposition….Pages 436-447
A new approach to resultant computations and other algorithms with exact division….Pages 448-459
Testing equivalence of morphisms on context-free languages….Pages 460-470
Work-time optimal parallel prefix matching….Pages 471-482
On the exact complexity of the string prefix-matching problem….Pages 483-494
Incremental text editing: a new data structure….Pages 495-507
The ESA ’93 Proceedings….Pages 508-508
Reviews
There are no reviews yet.