Below is the list of accepted papers to SODA, together with
a tentative schedule (If you are speaking,
PLEASE be sure to check the final schedule
that will appear in November, in case of changes later).   

There were 246 submissions, of which 84 were accepted.  
On behalf of the program committee, I thank all those who submitted
their papers. There were many more quality papers than 
the constraints of the schedule
and proceedings production allowed us to accept, and we regret
that we could not accept more of the papers.

Formal letters of acceptance and rejection will be sent out shortly.
Also, some comments from the committee will be sent out as well
(possibly in a separate mailing).


Michael Saks, Program Chair 1997 SODA.




20 minutes per talk, 5 minute break between talks for moving between sessions.

Sunday
Session I. 8:50-10:25 (4 talks)
10:25-10:50 (break)
Session II.10:50-12:25 (4 talks)
12:30-2:00 (lunch)
Plenary Session 2:00-3:00 
     Algorithms in Information Retrieval
           Prabhakar Raghavan, IBM Almaden Research Center
Session III. 3:05-4:15 (3 talks)
4:15-4:40 (break)
Session  IV. 4:40-5:50 (3 talks)

Monday
Session I. 8:30-10:05 (4 talks)
10:05-10:25 (break)
Session II.
10:25-12:25 (5 talks)
12:30-2:00 (lunch)
Plenary Session 2:00-3:00 
   From Sir Isaac to the Sloan Survey---Calculating the Structure and Chaos of
   Gravity in the Universe
          Professor George Lake, 
          Department of Astronomy and Physics, 
          University of Washington
Session III. 3:05-4:15 (3 talks)
4:15-4:40 (break)
Session IV. 4:40-5:50 (3 talks)

Tuesday
Session I. 8:30-10:05 (4 talks)
10:05-10:25 (break)
Session II. 10:25-12:25 (5 talks)
12:30-2:00 (lunch)
Session III. 2:00-3:35 (4 talks)

Sunday

SunIA.(4 talks)

Linear-time transitive orientation
      Ross M. McConnell and Jeremy P. Spinrad

Efficient and practical modular decomposition
     Elias Dahlhaus, Jens Gustedt and Ross McConnell 

Computing a minimum biclique cover is polynomial for bipartite 
  domino-free graphs
       J. Amilhastre, P. Janssen and M.C. Vilarem

A Combinatorial Algorithm for the Determinant 
     Meena Mahajan and V Vinay 


SunIB.(4 talks)

On page migration and other relaxed task systems
     Yair Bartal, Moses Charikar and Piotr Indyk

Online list accessing algorithms and their applications
     Ran Bachrach and Ran El-Yaniv

Experimental studies of access graph based heuristics: Beating the LRU standard
      Amos Fiat and Ziv Rosen

The k-client problem
     H. Alborzi, A-H. Esfahanian, F. Kivanc, E. Torng, 
     P.  Uthaisombut and S. Wagner 


SunIIA.  (4 talks)

Buckets, heaps, lists and monotone priority queues
     Boris V. Cherkassky, Andrew V. Goldberg and Craig Silverstein 

All Pairs Small Stretch Paths
     Edith Cohen and Uri Zwick

Approximating shallow-light trees
     Guy Kortsarz and David Peleg

Self-Stabilizing Unidirectional Network Algorithms by Power-Supply
     Yehuda Afek and Anat Bremler 



SunIIB. (4 talks)

Efficient Approx and Optimization algorithms for Computational metrology
      Christian A. Duncan, Michael T. Goodrich, and Edgar A. Ramos 

Faster construction of planar two-centers
      David Eppstein

An efficient algorithm for terrain simplification
     Pankaj Agarwal and Pavan Desikan

Map labeling and its generalizations
     S. Doddi, M. Marathe, A. Mirzaian, B. Moret, and B. Zhu 



SunIIIA.  (3 talks)

On-line algorithms for compressing planar curves
     Gordon T. Wilfong

A competitive Strategy for Learning a Polygon
     Frank Hoffmann, Christian Icking, Rolf Kleina and Klaus Kriegel 

Online difference maximization
      Ming-Yang Kao and Stephen R. Tate 


SunIIIB.  (3 talks)

Randomly sampling molecules
     Leslie Ann Goldberg and Mark Jerrum

Simple Markov chain algs. for generating bipartite graphs and tournaments
     Ravi Kannan, Prasad Tetali and Santosh Vempala 

The Path Resistance Method for Bounding \lambda_2 of a Laplacian
     Stephen Guattery, Tom Leighton and Gary L. Miller 



SunIVA. (3 talks)

On the maximum scatter TSP
     Esther M. Arkin, Yi-Jen Chiang, Joseph S.B. Mitchell, Steven S. Skiena
     and Tae-Chen Yang

The angular-metric traveling salesman problem
     A. Aggarwal, D. Coppersmith, S.  Khanna, R. Motwani and B. Schieber 

Shortest path in complete bipartite digraph problem and its applications
     X. He and  Z-Z Chen

SunIVB.  (3 talks)

Markov chains for linear extensions, the two-dimensional case
      Stefan Felsner and Lorenz Wernisch

Graph orientations with no sink and an approximation for a hard case 
    of #SAT
      Russ Bubley and Martin Dyer

New algorithms for planar lattice structures
      David B. Wilson


Monday
MonIA.(4 talks)

The variance of two game tree algorithms
      Yanjun Zhang

Nearly optimal distributed edge colouring in O(loglog n) rounds
     David A. Grable and Alessandro Panconesi

Probabilistic analysis for scheduling with conflicts
     Sandy Irani and Vitus Leung 

The Algorithmic Aspects of Uncrowded Hypergraphs
     Claudia Bertram-Kretzberg and Hanno Lefmann 




MonIB.(4 talks)

Decremental dynamic connectivity
      Mikkel Thorup 

An experimental analysis of Dynamic Minimum Spanning Tree algorithms
     Giuseppe Amato, Giuseppe Cattaneo and Giuseppe F. Italiano

Experimental Study of Minimum Cut Algorithms, 
      C. S. Chekuri, A. V. Goldberg, D. Karger, M. S. Levine and Cliff Stein

Implementing an FPTAS for all-terminal network reliability
      David R. Karger and Ray P.  Tai 



MonIIA.(5 talks)

Faster and simpler algorithm for sorting signed permutations by reversals
     Haim Kaplan, Ron Shamir and Robert Tarjan 

Randomized sorting in O(nloglog n) time and linear space ...
      Mikkel Thorup

Fast algorithms for sorting and searching strings
      Jon L. Bentley and Robert Sedgewick

The influence of Caches on the Performance of Sorting
     Anthony LaMarca and Richard E. Ladner

Runtime prediction of real programs on real machines
     Ulrich Finkler and Kurt Mehlhorn

MonIIB.(5 talks)

Local Rules for Protein Folding on the triangular lattice and 
     generalized hydrophobicity in the HP Model
          Richa Agarwala, Serafim Batzoglou, Scott Decatur, Vlado Dancik, 
          Martin Farach, Sridhar Hannenhalli, and Steven Skiena 

Mapping clones with a given ordering or interleaving
     Tao Jiang and Richard M. Karp

Numerical taxonomy on Data:Experimental results
     Jaime Cohen and Martin Farach

Inferring evolutionary trees from ordinal data
     P. Kearney, R. Hayward and H. Meijer

On distances between phylogenetic trees
     B. DasGupta, X. He, T. Jiang, M. Li, J. Tromp and L. Zhang 








MonIIIA.(3 talks)

Improved access to optical bandwidth in trees
     Vijay Kumar and Eric J. Schwabe

Optimal bounds for matching routing on trees
     Louxin Zhang

Efficient algorithms for finding disjoint paths in grids 
     Win-Tat Chan and Francis Y.L. Chin

MonIIIB.(3 talks)

Deterministic algorithms for 2-d convex programming and 3-d online LP
     Timothy M. Chan

A practical approx algorithm for LMS Line estimator
     David M. Mount, Nathan S. Netanyahu, Kathleen Romanik, 
     Ruth Silverman and Angela Y. Wu

Line transversals of balls and smallest enclosing cyl. in three dims.
     Pankaj K. Agarwal, Boris Aronov and Micha Sharir 


MonIVA.(3 talks)

Approximation Schemes for Scheduling
      Noga Alon, Yossi Azar and Tal Yadid 

Approx algorithms for the discrete time-cost tradeoff problem
      Martin Skutella

Poly. Algs. for multiprocessor scheduling with a small number of job lengths
      S. Thomas McCormick, Scott R. Smallwood and Frits C.R. Spieksma 

MonIVB.(3 talks)

A Near-Optimal Heuristic for Minimum weight triangulation of convex polygons
       Christos Levcopoulos and Drago Krznaric 

Optimal point placement for mesh smoothing
       Nina Amenta, Marshall Bern and David Eppstein 

Optimal Good-Aspect-Ratio coarsening for Unstructured Meshes
       Gary L. Miller, Dafna Talmor and Shang-Hua Teng

Tuesday
TueIA.(4 talks)

Coloring with defect
      Lenore Cowen, Wayne Goddard and Esther Jesurum 

Approximation Algorithms for the Achromatic Number
     Amitabh Chaudhary and Sundar Vishwanathan 

The Growth Rate of Vertex-Transitive Planar Graphs
     Laszlo Babai

Practical Toroidality Testing
     Eugene Neufeld and Wendy Myrvold


TueIB.(4 talks)

Approximation algorithms for precedence-constrained scheduling problems...
      Fabian A. Chudak and David B. Shmoys

Improved approximation algorithms for scheduling with release dates
      Michel X. Goemans

Better Approximation Guarantees for Job-Shop Scheduling
     Leslie Ann Goldberg, Mike Paterson, 
     Aravind Srinivasan, and Elizabeth Sweedyk 

Approximation techniques for average completion time scheduling
        Chandra Chekuri, Rajeev Motwani, Balas Natarajan and Cliff Stein 


TueIIA.(5 talks)

Buy-at-Bulk Network Design:Approximating the single-sink edge installation 
    problem
        F.S.Salman, J.Cheriyan, R.Ravi and S.Subramanian 

A better approximation ratio for the k-edge-connected spanning 
    subgraph problem
       Cristina G. Fernandes 

Fast spreading metric based approximate graph partitioning algorithms
     Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

Computing edge-connectivity augmentation function in O(nm) time
    Hiroshi Nagamochi, Takashi Shiraki and Toshihide Ibaraki 

Efficient algorithms for robustness in matroid optimization
     Greg N. Frederickson and Roberto Solis-Oba 



TueIIB.(5 talks)

Codes for Asynchronous Channels
        Leonard Schulman and David Zuckerman

Rounding in lattices and its cryptographic applications
        Dan Boneh and Ramarathnam Venkatesan 

Approximating matrix multiplication for pattern recognition tasks
       Edith Cohen and David D.  Lewis 

Improving the discrepancy bound for sparse matrices:better 
    approximations for sparse lattice approximation problems 
        Aravind Srinivasan

A strong and easily computable separation bound for arithm. expressions 
involving square roots,
        C.Burnikel and R.Fleischer and K.Mehlhorn and S.Schirra 


TueIIIA.(4 talks)

LP based approach to optimal stable matchings
     C.P. Teo and V.S. Jayachandran

Combinatorial Optimization Games
      Xiaotie Deng,Toshihide Ibaraki and Hiroshi Nagamochi

Optimal Search in Trees
      Yosi Ben-Asher, Eitan Farchi, and Ilan Newman 

TueIIIB. (4 talks)

Data structures for mobile data
     J. Basch and L. J. Guibas and J. Hershberger 

Methods for achieving fast query times in point location data structures
     M.T.Goodrich, M. Orletsky and K. Ramaiyer

Randomized fully-scalable BSP techniques for multi-searching and conv. hull
     Michael T. Goodrich

Partial matching of planar polylines under similarity transformations
     Scott D. Cohen and Leonidas J. Guibas