Algorithms and Computation: 4th International Symposium, ISAAC '93, Hong Kong, December 15-17, 1993. Proceedings [Paperback]

This volume presents the proceedings of the fourth annualInternational Symposium on Algorithms and Computation, heldin Hong Kong in December 1993.Numerous selected paperspresent original research in such areas as design andanalysis of algorithms, computational complexity, and theoryof computation. Topics covered include:- automata, languages, and computability,- combinatorial, graph, geometric, and randomizedalgorithms,- networks and distributed algorithms,- VLSIand parallel algorithms,- theory of learning and robotics,- number theory and robotics.Three invited papers are also included.Reaching a goal with directional uncertainty.- Constructing degree-3 spanners with other sparseness properties.- Remembering conflicts in history yields dynamic algorithms.- Coloring random graphs in polynomial expected time.- Graphical degree sequence problems with connectivity requirements.- How to treat delete requests in semi-online problems.- Finding the shortest watchman route in a simple polygon.- Constructing shortest watchman routes by divide-and-conquer.- A graph coloring result and its consequences for some guarding problems.- The maximum k-dependent and f-dependent set problem.- Finding shortest non-crossing rectilinear paths in plane regions.- Treewidth of circle graphs.- A framework for constructing heap-like structures in-place.- Double-ended binomial queues.- A simple balanced search tree with O(1) worst-case update time.- Mapping dynamic data and algorithm structures into product networks.- Permutation routing on reconfigurable meshes.- Adaptive and oblivious algorithms for d-cube permutation routing.- On quadratic lattice approximations.- A 2/3-approximation of the matroid matching problem.- Using fractal geometry for solving divide-and-conquer recurrences.- Simple combinatorial Gray codes constructed by reversing sublists.- Time space tradeoffs (getting closer to the barrier?).- Separating exponentially ambiguous NFA frolc*