Algorithms and Data Structures: Third Workshop, WADS ’93 Montréal, Canada, August 11–13, 1993 Proceedings

Mikhail J. Atallah, Danny Z. Chen (auth.), Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro, Sue Whitesides (eds.)3540571558, 9783540571551

The papers in this volume were presented at the Third Workshop on Algorithmsand Data Structures (WADS ’93), held in Montreal, Canada, August 1993. The volume opens with five invited presentations: “Computing the all-pairs longest chains in the plane” by M.J. Atallah and D.Z. Chen, “Towards a better understanding of pure packet routing” by A. Borodin, “Tolerating faults in meshes and other networks” (abstract) by R. Cole, “A generalization of binary search” by R.M. Karp, and “Groups and algebraic complexity” (abstract) by A.C. Yao. The volume continues with 52 regular presentations selected from 165 submissions, each of which was evaluated by at least three program committee members, many of whom called upon additional reviewers.

---

Table of contents :
Computing the all-pairs longest chains in the plane….Pages 1-13
Towards a better understanding of pure packet routing….Pages 14-25
Tolerating faults in meshes and other networks….Pages 26-26
A generalization of binary search….Pages 27-34
Groups and algebraic complexity….Pages 35-35
Connected component and simple polygon intersection searching….Pages 36-47
An optimal algorithm for finding the separation of simple polygons….Pages 48-59
Balanced search trees made simple….Pages 60-71
Probing a set of hyperplanes by lines and related problems….Pages 72-82
A general lower bound on the I/O-complexity of comparison-based algorithms….Pages 83-94
Point probe decision trees for geometric concept classes….Pages 95-106
A dynamic separator algorithm….Pages 107-118
Online load balancing of temporary tasks….Pages 119-130
Connected domination and steiner set on asteroidal triple-free graphs….Pages 131-141
The complexity of finding certain trees in tournaments….Pages 142-150
Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract)….Pages 151-162
Separating the power of EREW and CREW PRAMs with small communication width….Pages 163-174
Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs….Pages 175-187
Parallel construction of quadtrees and quality triangulations….Pages 188-199
Pattern matching for permutations….Pages 200-209
Filling polyhedral molds….Pages 210-221
Deferred-query—An efficient approach for problems on interval and circular-arc graphs….Pages 222-233
On the complexity of graph embeddings….Pages 234-245
Algorithms for polytope covering and approximation….Pages 246-252
Global strategies for augmenting the efficiency of TSP heuristics….Pages 253-264
Static and dynamic algorithms for k -point clustering problems….Pages 265-276
Scalable algorithms for bichromatic line segment intersection problems on Coarse Grained Multicomputers….Pages 277-288
Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)….Pages 289-301
The K -D heap: An efficient multi-dimensional priority queue….Pages 302-313
A complete and efficient algorithm for the intersection of a general and a convex polyhedron….Pages 314-324
Computing the smallest k -enclosing circle and related problems….Pages 325-336
An index data structure for matrices, with applications to fast two-dimensional pattern matching….Pages 337-348
A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects….Pages 349-360
Further results on generalized intersection searching problems: Counting, reporting, and dynamization….Pages 361-372
Generalized approximate algorithms for point set congruence….Pages 373-384
Approximating shortest superstrings with constraints….Pages 385-396
Tree reconstruction from partial orders….Pages 397-408
Improved parallel depth-first search in undirected planar graphs….Pages 409-420
On approximating the longest path in a graph….Pages 421-432
Designing multi-commodity flow trees….Pages 433-441
A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs….Pages 442-451
On fat partitioning, fat covering and the union size of polygons….Pages 452-463
A time-randomness tradeoff for selection in parallel….Pages 464-470
Detecting race conditions in parallel programs that use one semaphore….Pages 471-482
An algorithm for finding predecessors in integer sets….Pages 483-493
The exhaustion of shared memory: Stochastic results….Pages 494-505
Minimum weight euclidean matching and weighted relative neighborhood graphs….Pages 506-517
Efficient approximate shortest-path queries among isothetic rectangular obstacles….Pages 518-529
Counting and reporting red/blue segment intersections….Pages 530-540
Repetitive hidden-surface-removal for polyhedral scenes….Pages 541-552
On reconfigurability of VLSI linear arrays….Pages 553-564
Reconstructing strings from substrings (Extended abstract)….Pages 565-576
Combinatorial complexity of signed discs….Pages 577-588
Fast algorithms for one-dimensionsal compaction with jog insertion….Pages 589-600
An optimal algorithm for roundness determination on convex polygons….Pages 601-609
Practical algorithms on partial k -trees with an application to domination-like problems….Pages 610-621
Greedy algorithms for the on-line steiner tree and generalized steiner problems….Pages 622-633