aggarwa@IBM.COM (Alok Aggarwal) (10/03/90)
ACCEPTED PAPERS FOR SODA - 1991
Dynamic Expression Trees and Their Applications
Robert F. Cohen and Roberto Tamassia, Brown Univ.
Efficient 2-Dimensional Approximate Matching of
Non-rectangular Figures
Amihood Amir and Martin Farach, Univ. of Maryland
Approximating the Number of Solutions of a GF[2] Polynomial
Marek Karpinski, Univ. of Bonn, Germany and International
Computer Science Inst., Berkeley; and Michael Luby,
International Computer Science Inst.
A Fast Algorithm for Connecting Grid Points to the Boundary
With Nonintersecting Straight Lines
Yitzhak Birk and Jeffrey B. Lotspiech, IBM Research Division,
Almaden Research Center
A Strongly Polynomial Minimum Mean Cut Cancelling Algorithm
for Submodular Flow
S. Thomas McCormick, Univ. of British Columbia
Maintaining the Minimal Distance of a Point Set in
Polylogarithmic Time
Michiel Smid, Universitat des Saarlandes, Germany
Parallel Complexity of Tridiagonal Symmetric Eigenvalue
Problem
Dario Bini, Universita di Pisa;
Victor Pan, Columbia Univ. and Lehman College, CUNY
Space-efficient Ray-shooting and Intersection Searching:
Algorithms, Dynamization, and Applications
Siu Wing Cheng and Ravi Janardan, Univ. of Minnesota
Approximation Algorithms for Planar Traveling Salesman Tours
and Minimum-Length Triangulations
Kenneth L. Clarkson, AT&T Bell Labs.
Routing Through a Dense Channel With Minimum Total Wire
Length
Michael Formann, Freie Universitat Berlin, Germany; Dorothea
Wagner, Technische Universitat Berlin, Germany; and Frank
Wagner, Freie Universitat Berlin, Germany
Finding Stabbing Lines in 3-Dimensional Space
M. Pellegrini, Courant Institute;
P. Shor, AT&T Bell Labs.
The First Classical Ramsey Number for Hypergraphs Is
Computed
Brendan D. McKay, Australian National University;
Stanislaw P. Radziszowski, Rochester Inst. of Technology
Optimal Algorithms for Partitioning Trees
Greg N. Frederickson, Purdue Univ.
An Efficient Parallel Algorithm for the Row Minima of a
Totally Monotone Matrix
Mikhail J. Atallah, Purdue Univ.;
S. Rao Kosaraju, Johns Hopkins Univ.
Tight Bounds on the Complexity of the Boyer-Moore String
Matching Algorithm
Richard Cole, Courant Institute
On Finding Minimal Two-Connected Subgraphs
Pierre Kelsen and Vijaya Ramachandran, Univ. of
Texas, Austin
Edge Coloring Planar Graphs with Two Outerplanar
Subgraphs
Lenwood S. Heath, Virginia Polytechnic Inst.
Recognizing Strong Connectivity in Periodic Graphs
and Its Relation to Integer Programaming
Muralidharan Kodialam and James B. Orlin, MIT
Optimal Time Randomized Consensus - Making Resilient
Algorithms Fast in Practice
Michael Saks, Univ. of California, San Diego; Nir Shavit,
IBM Research Division, Almaden Research Center;
Heather Woll, Univ. of California, San Diego
On Partitions and Presortedness of Sequences
Jingsen Chen and Svante Carlsson, Lund University, Sweden
Complexity Results and Algorithms
for {<,<=,=}-Constrained Scheduling
Bonnie Berger and Lenore Cowen, MIT
The Fourth Moment Method
Bonnie Berger, MIT
The Canadian Traveller Problem
Amotz Bar-Noy and Baruch Schieber, IBM Research Division,
T. W. Watson Research Center
On-Line Weighted Matching
Bala Kalyanasundaram and Kirk Pruhs, Univ. of Pittsburgh
Offline Maintenance of Planar Configurations
John Hershberger, Digital Equipment Corp. Systems
Research Center; Subhash Suri, Bell Communications Research
A New Lower Bound Technique and its Application
Prakash Ramanan, Univ, of California, Santa Barbara
Lower Bounds for On-Line Tree Embeddings
Panfeng Liu and David Greenberg, Yale Univ.;
Sandeep Bhatt, California Institute of Technology
On-Line Caching as Cache Size Varies
Neal E. Young, Princeton Univ.
On the Parallel Complexity of Evaluating Game-Trees
Andrei Z. Broder and Anna R. Karlin, Digital Equipment
Corp. Systems Research Center; Prabhakar Raghavan,
IBM Research Division, T. J. Watson Research Center;
Eli Upfal, IBM Research Division, Almaden Research Center
Efficient Sequential and Parallel Algorithms for Computing
Recovery Points in Trees and Paths
Marek Chrobak, Univ. of California, Riverside; David
Eppstein, Xerox PARC and Univ. of California, Irvine;
Giuseppe F. Italiano, Columbia Univ. and Universita di
Roma; Moti Yung, IBM Research Division,
T. J. Watson Research Center
Time-Work Tradeoffs for Parallel Graph Algorithms
Thomas H. Spencer, Rensselaer Polytechnic Inst.
Bounded Space On-Line Bin Packing: Best is Better than
First
J. Csirik, Bolyai Inst., Hungary; David S. Johnson,
AT&T Bell Labs.
Upward Planar Drawing of Single Source Acyclic Digraphs
Michael Hutton and Anna Lubiw, Univ. of Waterloo, Canada
Density Graphs and Separators
Gary L. Miller, Carnegie Mellon Univ. and Univ. of
Southern California; Stephen A. Vavasis, Cornell Univ.
Triangulating Three-Colored Graphs
Sampath K. Kannan and Tandy J. Warnow, Univ. of
California, Berkeley
Adaptive Heuristics for Binary Search Trees and Constant
Linkage Cost
Tony W. Lai and Derick Wood, Univ. of Waterloo, Canada
Matching Points into Noise Regions: Combinatorial Bounds
and Algorithms
Esther M. Arkin, Cornell Univ.; Klara Kedem, Tel Aviv
Univ.; Joseph S. B. Mitchell, Cornell Univ.;
Josef Sprinzak and Michael Werman, Hebrew University
Improved Approximation Algorithms for Shop Scheduling
Problems
David B. Shmoys, Cornell Univ.; Clifford Stein and
Joel Wein, MIT
Randomized Competitive Algorithms for the List Update
Problem
Sandra Irani, Univ. of California, Berkeley;
Nick Reingold and Jeffery Westbrook, Yale Univ.;
Daniel Sleator, Carnegie Mellon Univ.
A Sublinear Randomized Parallel Algorithm for the Maximum
Clique Problem in Perfect Graphs
Farid Alizadeh, Univ. of Minnesota
Decomposing Graphs Into Regions of Small Diameter
Nathan Linial, Hebrew Univ.;
Michael Saks, Univ. of California, San Diego
On the Complexity of Some Flow Problems
Edith Cohen, Stanford Univ. and IBM Almaden Division,
Almaden Research Center;
Nimrod Megiddo, IBM Research Division, Almaden Research Center and
Tel Aviv Univ.
Ultra-Fast Expected Time Parallel Algorithms
Philip D. MacKenzie and Quentin F. Stout, Univ. of Michigan
Persistence, Amortization and Randomization
Paul F. Dietz and Rajeev Raman, Univ. of Rochester
An O(n^2) Time Algorithm for the 2-Chain Cover Problem
and Related Problems
Tze-heng Ma and Jeremy Spinrad, Vanderbilt Univ.
Learning the Fourier Spectrum of Probabilistic Lists and
Trees
William Aiello and Milena Mihail, Bell Communications
Research, Morristown
Circular Hulls and Orbiforms of Simple Polygons
V. Chandru, Purdue Univ.;
R. Venkataraman, Indian Inst. of Science
Computing a Face in an Arrangement of Line Segments
Bernard Chazelle, Princeton Univ.; Herbert Edelsbrunner,
Univ. of Illinois, Urbana; Leonidas J. Guibas, Digital
Equipment Corp. Systems Research Center, MIT
and Stanford Univ.; Micha Sharir,
Tel Aviv Univ., and Courant; Jack Snoeyink,
Stanford Univ.
Tight Bounds on the Number of Minimum-Mean Cycle
Cancellations
Tomasz Radzik and Andrew V. Goldberg, Stanford Univ.
Fast Hashing on PRAM
Joseph Gil, Hebrew Univ.; Yossi Matias,
Tel-Aviv Univ.
Planar Geometric Location Problems and Maintaining the
Width of a Planar Set
Pankaj K. Agarwal, DIMACS and Rutgers Univ.; Micha Sharir,
Tel-Aviv Univ. and Courant
Fully Persistent Lists with Catenation
James R. Driscoll, Dartmouth College; Daniel D. K. Sleator,
Carnegie Mellon Univ.; Robert E. Tarjan, Princeton Univ.
The Aquarium Keeper's Problem
Jurek Czyzowicz, Universite du Quebec a Hull; Peter
Egyed and Hazel Everett, McGill Univ., Canada; David
Rappaport, Queen's Univ., Canada; Thomas Shermer, Simon
Fraser Univ. Canada; Diane Souvaine, Rutgers Univ.;
Godfried Toussaint, McGill Univ., Canada; Jorge
Urrutia, Univ. of Ottawa
The Analysis of Multidimensional Searching in Quad-Trees
Philippe Flajolet, INRIA, France; Gaston Gonnet,
Eidgen Tech Hochschule, Switzerland; Claude Puech, ENS,
France; Mike Robson, Australian National Univ.