ISA'91 Algorithms: 2nd International Symposium on Algorithms Taipei, Republic of China, December 16–18, 1991 Proceedings

Decision-making with incomplete information....Pages 1-1
Maximum independet set of a permutation graph in k tracks....Pages 2-11
Algorithms for square roots of graphs....Pages 12-21
Distributed k-mutual exclusion problem and k-coteries....Pages 22-31
Is the shuffle-exchange better than the butterfly?....Pages 32-41
Weighted random assignments with application to hashing....Pages 42-42
Scheduling file transfers under port and channel constraints....Pages 43-51
Substitution decomposition on chordal graphs and applications....Pages 52-60
Mixed-searching and proper-path-width....Pages 61-71
Short wire routing in convex grids....Pages 72-82
A new approach to knock-knee channel routing....Pages 83-93
Circuit partitioning algorithms: Graph model versus geometry model....Pages 94-103
Identifying 2-monotonic positive boolean functions in polynomial time....Pages 104-115
An average case analysis of Monien and Speckenmeyer\'s mechanical theorem proving algorithm....Pages 116-126
An on-line algorithm for navigating in unknown terrain....Pages 127-136
On maintaining the width and diameter of a planar point-set online....Pages 137-149
Optimal triangulations by retriangulating....Pages 150-150
Approximating polygons and subdivisions with minimum link paths....Pages 151-162
An incremental algorithm for constructing shortest watchman routes....Pages 163-175
On hitting grid points in a convex polygon with straight lines....Pages 176-189
On the complexity of some Hamiltonian and Eulerian problems in edge-colored complete graphs....Pages 190-198
Dynamic programming on intervals....Pages 199-207
Combinatorial optimization through order statistics....Pages 208-217
Combinatorics and algorithms of geometric arrangements....Pages 218-218
An analysis of randomized shear sort on the mesh computer....Pages 219-228
Efficient parallel divide-and-conquer for a class of interconnection topologies....Pages 229-240
Optimal specified root embedding of full binary trees in faulty hypercubes....Pages 241-250
A tight lower bound for the worst case of Bottom-Up-Heapsort....Pages 251-262
Historical searching and sorting....Pages 263-272
Comparison-efficient and write-optimal searching and sorting....Pages 273-282
Nearest neighbors revisited....Pages 283-283
Competitiveness and response time in on-line algorithms....Pages 284-293
A linear time optimal via assignment algorithm for Three-Dimensional channel routing....Pages 294-307
Symmetry of information and one-way functions....Pages 308-315
A linear time algorithm to recognize the double euler trail for series-parallel networks....Pages 316-325
On finding a smallest augmentation to biconnect a graph (Extended abstract)....Pages 326-335
A faster algorithm for edge-disjoint paths in planar graphs....Pages 336-348
An optimal construction method for generalized convex layers....Pages 349-363
Rectangular point location and the dynamic closest pair problem....Pages 364-374
Parallel algorithms for some dominance problems based on a CREW PRAM....Pages 375-384
Parallel algorithms for finding maximal k -dependent sets and maximal f -matchings....Pages 385-395