Algorithms and Computation: 4th International Symposium, ISAAC '93 Hong Kong, December 15–17, 1993 Proceedings

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