Algorithms and Computation: 4th International Symposium, ISAAC '93, Hong Kong, December 15-17, 1993. Proceedings (Lecture Notes in Computer Science, 762)

This volume presents the proceedings of the fourth annual International Symposium on Algorithms and Computation, held in Hong Kong in December 1993.Numerous selected papers present original research in such areas as design and analysis of algorithms, computational complexity, and theory of computation. Topics covered include: - automata, languages, and computability, - combinatorial, graph, geometric, and randomized algorithms, - 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....Pages 1-10 Constructing degree-3 spanners with other sparseness properties....Pages 11-20 Remembering conflicts in history yields dynamic algorithms....Pages 21-30 Coloring random graphs in polynomial expected time....Pages 31-37 Graphical degree sequence problems with connectivity requirements....Pages 38-47 How to treat delete requests in semi-online problems....Pages 48-57 Finding the shortest watchman route in a simple polygon....Pages 58-67 Constructing shortest watchman routes by divide-and-conquer....Pages 68-77 A graph coloring result and its consequences for some guarding problems....Pages 78-87 The maximum k -dependent and f -dependent set problem....Pages 88-97 Finding shortest non-crossing rectilinear paths in plane regions....Pages 98-107 Treewidth of circle graphs....Pages 108-117 A framework for constructing heap-like structures in-place....Pages 118-127 Double-ended binomial queues....Pages 128-137 A simple balanced search tree with O (1) worst-case update time....Pages 138-146 Mapping dynamic data and algorithm structures into product networks....Pages 147-156 Permutation routing on reconfigurable meshes....Pages 157-166 Adaptive and oblivious algorithms for d-cube permutation routing....Pages 167-175 On quadratic lattice approximations....Pages 176-184 A 2/3-approximation of the matroid matching problem....Pages 185-190 Using fractal geometry for solving divide-and-conquer recurrences....Pages 191-200 Simple combinatorial Gray codes constructed by reversing sublists....Pages 201-208 Time space tradeoffs (getting closer to the barrier?)....Pages 209-220 Separating exponentially ambiguous NFA from polynomially ambiguous NFA....Pages 221-229 Threshold computation and cryptographic security....Pages 230-239 On the Power of reading and writing simultaneously in parallel computations....Pages 240-249 Relativizing complexity classes with Random Oracles....Pages 250-258 An introduction to perpetual gossiping....Pages 259-266 A probabilistic selection network with butterfly networks....Pages 267-276 Optimal group gossiping in hypercubes under wormhole routing model....Pages 277-286 Optimal linear broadcast routing with capacity limitations....Pages 287-296 Multicommodity flows: A survey of recent research....Pages 297-302 Parallel construction of canonical ordering and convex drawing of triconnected planar graphs....Pages 303-312 Number theory helps line detection in digital images an extended abstract....Pages 313-322 Optimally computing the shortest weakly visible subedge of a simple polygon preliminary version....Pages 323-332 Multicommodity flows in even, planar networks....Pages 333-342 Linear time algorithms for disjoint Two-Face Paths Problems in planar graphs....Pages 343-352 Robot mapping: Foot-prints vs tokens....Pages 353-362 Recent developments on the approximability of combinatorial problems....Pages 363-368 On the relationship among cryptographic physical assumptions....Pages 369-378 Separating complexity classes related to bounded alternating Ω-branching programs....Pages 379-388 The complexity of the optimal variable ordering problems of shared binary decision diagrams....Pages 389-398 On Horn envelopes and hypergraph transversals....Pages 399-405 Page migration algorithms using work functions....Pages 406-415 Memory paging for connectivity and path problems in graphs....Pages 416-425 Randomized competitive algorithms for successful and unsuccessful search on self-adjusting linear lists....Pages 426-435 Randomized on-line algorithms for the page replication problem....Pages 436-445 New algorithms for minimizing the longest wire length during circuit compaction....Pages 446-455 Parallel algorithms for single-layer channel routing....Pages 456-465 Consecutive interval query and dynamic programming on intervals....Pages 466-475 An improved algorithm for the traveler's problem....Pages 476-485 Vehicle scheduling on a tree with release and handling times....Pages 486-495 Scheduling algorithms for a chain-like task system....Pages 496-505 Weighted independent perfect domination on cocomparability graphs....Pages 506-514 Plane sweep algorithms for the polygonal approximation problems with applications....Pages 515-522 Optimal rectilinear steiner tree for extremal point sets....Pages 523-532 Faster approximation algorithms for the rectilinear steiner tree problem....Pages 533-542 Annotation 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 This volume presents the proceedings of the fourth annual International Symposium on Algorithms and Computation, held in Hong Kong in December 1993. Numerous selected papers present original research in such areas as design and analysis of algorithms, computational complexity, and theory of computation. Topics covered include: - automata, languages, and computability, - combinatorial, graph, geometric, and randomized algorithms, - networks and distributed algorithms, - VLSIand parallel algorithms, - theory of learning and robotics, - number theory and robotics. Three invited papers are also included