8. SODA 1997: New Orleans, Louisiana

• George Lake, Thomas Quinn, Derek C. Richardson:
  From Sir Isaac to the Sloan Survey: Calculating the Structure and Chaos Owing to Gravity in the Universe. 1-10
  
• Prabhakar Raghavan:
  Information Retrieval Algorithms: A Survey. 11-18
  
• Ross M. McConnell, Jeremy Spinrad:
  Linear-Time Transitive Orientation. 19-25
  
• Elias Dahlhaus, Jens Gustedt, Ross M. McConnell:
  Efficient and Practical Modular Decomposition. 26-35
  
• Jérôme Amilhastre, Philippe Janssen, Marie-Catherine Vilarem:
  Computing a Minimum Biclique Cover is Polynomial for Bipartite Domino-Free Graphs. 36-42
  
• Yair Bartal, Moses Charikar, Piotr Indyk:
  On Page Migration and Other Related Task Systems. 43-52
  
• Ran Bachrach, Ran El-Yaniv:
  Online List Accessing Algorithms and Their Applications: Recent Empirical Evidence. 53-62
  
• Amos Fiat, Ziv Rosen:
  Experimental Studies of Access Graph Based Heuristics: Beating the LRU Standard? 63-72
  
• Houman Alborzi, Eric Torng, Patchrawat Uthaisombut, Stephen Wagner:
  The k-Client Problem. 73-82
  
• Boris V. Cherkassky, Andrew V. Goldberg, Craig Silverstein:
  Buckets, Heaps, Lists, and Monotone Priority Queues. 83-92
  
• Edith Cohen, Uri Zwick:
  All-Pairs Small-Stretch Paths. 93-102
  
• Guy Kortsarz, David Peleg:
  Approximating Shallow-Light Trees (Extended Abstract). 103-110
  
• Yehuda Afek, Anat Bremler-Barr:
  Self-Stabilizing Unidirectional Network Algorithms by Power-Supply (Extended Abstract). 111-120
  
• Christian A. Duncan, Michael T. Goodrich, Edgar A. Ramos:
  Efficient Approximation and Optimization Algorithms for Computational Metrology. 121-130
  
• David Eppstein:
  Faster Construction of Planar Two-Centers. 131-138
  
• Pankaj K. Agarwal, Pavan K. Desikan:
  An Efficient Algorithm for Terraine Simplification. 139-147
  
• Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Bernard M. E. Moret, Binhai Zhu:
  Map Labeling and Its Generalizations. 148-157
  
• Gordon T. Wilfong:
  On-line Algorithms for Compressing Planar Curves. 158-165
  
• Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel:
  A Competitive Strategy for Learning a Polygon. 166-174
  
• Ming-Yang Kao, Stephen R. Tate:
  On-Line Difference Maximization. 175-182
  
• Leslie Ann Goldberg, Mark Jerrum:
  Randomly Sampling Molecules. 183-192
  
• Ravi Kannan, Prasad Tetali, Santosh Vempala:
  Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract). 193-200
  
• Stephen Guattery, Frank Thomson Leighton, Gary L. Miller:
  The Path Resistance Method for Bounding lambda₂ of a Laplacian. 201-210
  
• Esther M. Arkin, Yi-Jen Chiang, Joseph S. B. Mitchell, Steven Skiena, Tae-Cheon Yang:
  On the Maximum Scatter TSP (Extended Abstract). 211-220
  
• Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber:
  The Angular-Metric Traveling Salesman Problem. 221-229
  
• Xin He, Zhi-Zhong Chen:
  Shortest Path in Complete Bipartite Digraph Problem and its Applications. 230-238
  
• Stefan Felsner, Lorenz Wernisch:
  Markov Chains for Linear Extensions, the Two-Dimensional Case. 239-247
  
• Russ Bubley, Martin E. Dyer:
  Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT. 248-257
  
• David Bruce Wilson:
  Determinant Algorithms for Random Planar Structures. 258-267
  
• Yanjun Zhang:
  The Variance of Two Game Tree Algorithms. 268-277
  
• David A. Grable, Alessandro Panconesi:
  Nearly Optimal Distributed Edge Colouring in O(log log n) Rounds. 278-285
  
• Sandy Irani, Vitus J. Leung:
  Probabilistic Analysis for Scheduling with Conflicts. 286-295
  
• Claudia Bertram-Kretzberg, Hanno Lefmann:
  The Algorithmic Aspects of Uncrowded Hypergraphs (Extended Abstract). 296-304
  
• Mikkel Thorup:
  Decremental Dynamic Connectivity. 305-313
  
• Giuseppe Amato II, Giuseppe Cattaneo, Giuseppe F. Italiano:
  Experimental Analysis of Dynamic Minimum Spanning Tree Algorithms (Extended Abstract). 314-323
  
• Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Clifford Stein:
  Experimental Study of Minimum Cut Algorithms. 324-333
  
• David R. Karger, Ray P. Tai:
  Implementing a Fully Polynomial Time Approximation Scheme for All Terminal Network Reliability. 334-343
  
• Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
  Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. 344-351
  
• Mikkel Thorup:
  Randomized sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-Wise Boolean Operations. 352-359
  
• Jon Louis Bentley, Robert Sedgewick:
  Fast Algorithms for Sorting and Searching Strings. 360-369
  
• Anthony LaMarca, Richard E. Ladner:
  The Influence of Caches on the Performance of Sorting. 370-379
  
• Ulrich Finkler, Kurt Mehlhorn:
  Runtime Prediction of Real Programs on Real Machines. 380-389
  
• Richa Agarwala, Serafim Batzoglou, Vlado Dancík, Scott E. Decatur, Martin Farach, Sridhar Hannenhalli, Steven Skiena:
  Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model. 390-399
  
• Tao Jiang, Richard M. Karp:
  Mapping Clones with a Given Ordering or Interleaving (Extended Abstract). 400-409
  
• Jaime Cohen, Martin Farach:
  Numerical Taxonomy on Data: Experimental Results. 410-417
  
• Paul E. Kearney, Ryan Hayward, Henk Meijer:
  Inferring Evolutionary Trees from Ordinal Data. 418-426
  
• Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang:
  On Distances between Phylogenetic Trees (Extended Abstract). 427-436
  
• Vijay Kumar, Eric J. Schwabe:
  Improved Access to Optimal Bandwidth in Trees. 437-444
  
• Louxin Zhang:
  Optimal Bounds for Matching Routing on Trees. 445-453
  
• Wun-Tat Chan, Francis Y. L. Chin:
  Efficient Algorithms for Finding Disjoint Paths in Grids (Extended Abstract). 454-463
  
• Timothy M. Chan:
  Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming. 464-472
  
• David M. Mount, Nathan S. Netanyahu, Kathleen Romanik, Ruth Silverman, Angela Y. Wu:
  A Practical Approximation Algorithm for the LMS Line Estimator. 473-482
  
• Pankaj K. Agarwal, Boris Aronov, Micha Sharir:
  Line Traversals of Balls and Smallest Enclosing Cylinders in Three Dimensions. 483-492
  
• Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid:
  Approximation Schemes for Scheduling. 493-500
  
• Martin Skutella:
  Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem. 501-508
  
• S. Thomas McCormick, Scott R. Smallwood, Frits C. R. Spieksma:
  Polynomial Algorithms for Multiprocessor Scheduling with a Small Number of Job Lengths. 509-517
  
• Christos Levcopoulos, Drago Krznaric:
  A Near-Optimal Heuristic for Minimum Weight Triangulation of Convex Polygons (Extended Abstract). 518-527
  
• Nina Amenta, Marshall W. Bern, David Eppstein:
  Optimal Point Placement for Mesh Smoothing. 528-537
  
• Gary L. Miller, Dafna Talmor, Shang-Hua Teng:
  Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes. 538-547
  
• Lenore Cowen, Wayne Goddard, C. E. Jesurum:
  Coloring with Defect. 548-557
  
• Amitabh Chaudhary, Sundar Vishwanathan:
  Approximation Algorithms for the Achromatic Number. 558-563
  
• László Babai:
  The Growth Rate of Vertex-Transitive Planar Graphs. 564-573
  
• Eugene Neufeld, Wendy J. Myrvold:
  Practical Toroidality Testing. 574-580
  
• Fabián A. Chudak, David B. Shmoys:
  Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract). 581-590
  
• Michel X. Goemans:
  Improved Approximation Algorithms for Scheduling with Release Dates. 591-598
  
• Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, Elizabeth Sweedyk:
  Better Approximation Guarantees for Job-shop Scheduling. 599-608
  
• Chandra Chekuri, Rajeev Motwani, B. Natarajan, Clifford Stein:
  Approximation Techniques for Average Completion Time Scheduling. 609-618
  
• F. Sibel Salman, Joseph Cheriyan, R. Ravi, S. Subramanian:
  Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem. 619-628
  
• Cristina G. Fernandes:
  A Better Approximation Ratio for the Minimum k-Edge-Connected Spanning Subgraph Problem. 629-638
  
• Guy Even, Joseph Naor, Satish Rao, Baruch Schieber:
  Fast Approximate Graph Partitioning Algorithms. 639-648
  
• Hiroshi Nagamochi, Takashi Shiraki, Toshihide Ibaraki:
  Computing Edge-Connectivity Augmentation Function in Õ(nm) Time. 649-658
  
• Greg N. Frederickson, Roberto Solis-Oba:
  Efficient Algorithms for Robustness in Matroid Optimization. 659-668
  
• Leonard J. Schulman, David Zuckerman:
  Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version). 669-674
  
• Dan Boneh, Ramarathnam Venkatesan:
  Rounding in Lattices and its Cryptographic Applications. 675-681
  
• Edith Cohen, David D. Lewis:
  Approximating Matrix Multiplication for Pattern Recognition Tasks. 682-691
  
• Aravind Srinivasan:
  Improving the Discrepancy Bound for Sparse Matrices: Better Approximations for Sparse Lattice Approximation Problems. 692-701
  
• Christoph Burnikel, Rudolf Fleischer, Kurt Mehlhorn, Stefan Schirra:
  A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Square Roots. 702-709
  
• Chung-Piaw Teo, Jay Sethuraman:
  LP Based Approach to Optimal Stable Matchings. 710-719
  
• Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi:
  Combinatorial Optimization Games. 720-729
  
• Meena Mahajan, V. Vinay:
  A Combinatorial Algorithm for the Determinant. 730-738
  
• Yosi Ben-Asher, Eitan Farchi, Ilan Newman:
  Optimal Search in Trees: Extended Abstract + Appendix. 739-746
  
• Julien Basch, Leonidas J. Guibas, John Hershberger:
  Data Structures for Mobile Data. 747-756
  
• Michael T. Goodrich, Mark W. Orletsky, Kumar Ramaiyer:
  Methods for Achieving Fast Query Times in Point Location Data Structures. 757-766
  
• Michael T. Goodrich:
  Randomized Fully-Scalable BSP Techniques for Multi-Searching and Convex Hull Construction (Preliminary Version). 767-776
  
• Scott D. Cohen, Leonidas J. Guibas:
  Partial Matching of Planar Polylines Under Similarity Transformations. 777-786
  

Last update Fri May 25 08:40:42 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page