This volume presents the proceedings of the Second Annual International Symposium on Algorithms held at Academia Sinica, Taipei, Republic of China, December 16-18, 1991. The symposium was organized by the Institute of Information Science, Academia Sinica, and the National Tsing Hua University. In response to the program committee's call for papers, 90 papers were submitted, from which the committee selected 36 for presentation at the symposium. In addition to these contributed papers, the symposium included 5 invited talks. The subjects of the papers range widely in the area of discrete algorithms, over such topics as computational geometry, graph algorithms, complexity theory, parallel algorithms, distributed computing and computational algebra.
Author(s): Christos H. Papadimitriou (auth.), Wen-Lian Hsu, R. C. T. Lee (eds.)
Series: Lecture Notes in Computer Science 557
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 1991
Language: English
Pages: 401
Tags: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Combinatorics; Probability Theory and Stochastic Processes; Statistics, general; Computer Graphics
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
