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