Description
Springer Algorithms and Data Structures Third Workshop WADS 93 Montreal Canada August 11-13 1993. Proceedings by Frank Dehne, Joerg-Rudiger Sack, Nicola Santoro, Sue Whitesides
The papers in this volume were presented at the Third_x000D_Workshop on Algorithmsand Data Structures (WADS '93), held_x000D_in Montreal, Canada, August 1993._x000D_The volume opens with five invited presentations: "Computing_x000D_the all-pairs longest chains in the plane" by M.J. Atallah_x000D_and D.Z. Chen, "Towards a better understanding of pure_x000D_packet routing" by A. Borodin, "Tolerating faults in meshes_x000D_and other networks" (abstract) by R. Cole, "A generalization_x000D_of binary search" by R.M. Karp, and "Groups and algebraic_x000D_complexity" (abstract) by A.C. Yao. The volume continues_x000D_with 52 regular presentations selected from 165 submissions,_x000D_each of which was evaluated by at least three program_x000D_committee members, many of whom called upon additional_x000D_reviewers._x000D_ Table of contents : - _x000D_
Computing the all-pairs longest chains in the plane.- Towards a better understanding of pure packet routing.- Tolerating faults in meshes and other networks.- A generalization of binary search.- Groups and algebraic complexity.- Connected component and simple polygon intersection searching.- An optimal algorithm for finding the separation of simple polygons.- Balanced search trees made simple.- Probing a set of hyperplanes by lines and related problems.- A general lower bound on the I/O-complexity of comparison-based algorithms.- Point probe decision trees for geometric concept classes.- A dynamic separator algorithm.- Online load balancing of temporary tasks.- Connected domination and steiner set on asteroidal triple-free graphs.- The complexity of finding certain trees in tournaments.- Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract).- Separating the power of EREW and CREW PRAMs with small communication width.- Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs.- Parallel construction of quadtrees and quality triangulations.- Pattern matching for permutations.- Filling polyhedral molds.- Deferred-query-An efficient approach for problems on interval and circular-arc graphs.- On the complexity of graph embeddings.- Algorithms for polytope covering and approximation.- Global strategies for augmenting the efficiency of TSP heuristics.- Static and dynamic algorithms for k-point clustering problems.- Scalable algorithms for bichromatic line segment intersection problems on Coarse Grained Multicomputers.- Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract).- The K-D heap: An efficient multi-dimensional priority queue.- A complete and efficient algorithm for the intersection of a general and a convex polyhedron.- Computing the smallest k-enclosing circle and related problems.- An index data structure for matrices, with applications to fast two-dimensional pattern matching.- A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects.- Further results on generalized intersection searching problems: Counting, reporting, and dynamization.- Generalized approximate algorithms for point set congruence.- Approximating shortest superstrings with constraints.- Tree reconstruction from partial orders.- Improved parallel depth-first search in undirected planar graphs.- On approximating the longest path in a graph.- Designing multi-commodity flow trees.- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs.- On fat partitioning, fat covering and the union size of polygons.- A time-randomness tradeoff for selection in parallel.- Detecting race conditions in parallel programs that use one semaphore.- An algorithm for finding predecessors in integer sets.- The exhaustion of shared memory: Stochastic results.- Minimum weight euclidean matching and weighted relative neighborhood graphs.- Efficient approximate shortest-path queries among isothetic rectangular obstacles.- Counting and reporting red/blue segment intersections.- Repetitive hidden-surface-removal for polyhedral scenes.- On reconfigurability of VLSI linear arrays.- Reconstructing strings from substrings (Extended abstract).- Combinatorial complexity of signed discs.- Fast algorithms for one-dimensionsal compaction with jog insertion.- An optimal algorithm for roundness determination on convex polygons.- Practical algorithms on partial k-trees with an application to domination-like problems.- Greedy algorithms for the on-line steiner tree and generalized steiner problems._x000D_