ISA '91 Algorithms

Decision-making with incomplete information.- Maximum independet set of a permutation graph in k tracks.- Algorithms for square roots of graphs.- Distributed k-mutual exclusion problem and k-coteries.- Is the shuffle-exchange better than the butterfly?.- Weighted random assignments with application to hashing.- Scheduling file transfers under port and channel constraints.- Substitution decomposition on chordal graphs and applications.- Mixed-searching and proper-path-width.- Short wire routing in convex grids.- A new approach to knock-knee channel routing.- Circuit partitioning algorithms: Graph model versus geometry model.- Identifying 2-monotonic positive boolean functions in polynomial time.- An average case analysis of Monien and Speckenmeyer's mechanical theorem proving algorithm.- An on-line algorithm for navigating in unknown terrain.- On maintaining the width and diameter of a planar point-set online.- Optimal triangulations by retriangulating.- Approximating polygons and subdivisions with minimum link paths.- An incremental algorithm for constructing shortest watchman routes.- On hitting grid points in a convex polygon with straight lines.- On the complexity of some Hamiltonian and Eulerian problems in edge-colored complete graphs.- Dynamic programming on intervals.- Combinatorial optimization through order statistics.- Combinatorics and algorithms of geometric arrangements.- An analysis of randomized shear sort on the mesh computer.- Efficient parallel divide-and-conquer for a class of interconnection topologies.- Optimal specified root embedding of full binary trees in faulty hypercubes.- A tight lower bound for the worst case of Bottom-Up-Heapsort.- Historical searching and sorting.- Comparison-efficient and write-optimal searching and sorting.- Nearest neighbors revisited.- Competitiveness and response time in on-line algorithms.- A linear time optimal via assignment algorithm for Three-Dimensional channel routing.- Symmetry of information and one-way functions.- A linear time algorithm to recognize the double euler trail for series-parallel networks.- On finding a smallest augmentation to biconnect a graph (Extended abstract).- A faster algorithm for edge-disjoint paths in planar graphs.- An optimal construction method for generalized convex layers.- Rectangular point location and the dynamic closest pair problem.- Parallel algorithms for some dominance problems based on a CREW PRAM.- Parallel algorithms for finding maximal k-dependent sets and maximal f-matchings.