Journal of the ACM, Volume 46, 1999

Volume 46, Number 1, January 1999

• Sridhar Hannenhalli, Pavel A. Pevzner:
  Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals. 1-27
  
• Zvi Galil, Giuseppe F. Italiano, Neil Sarnak:
  Fully Dynamic Planarity Testing with Applications. 28-91
  
• Elizabeth J. O'Neil, Patrick E. O'Neil, Gerhard Weikum:
  An Optimality Proof of the LRU-K Page Replacement Algorithm. 92-112
  
• Felipe Cucker, Steve Smale:
  Complexity Estimates Depending on Condition and Round-Off Error. 113-184
  

Volume 46, Number 2, March 1999

• Joel Hass, J. C. Lagarias, Nicholas Pippenger:
  The Computational Complexity of Knot and Link Problems. 185-211
  
• Bonnie Berger, Jon M. Kleinberg, Frank Thomson Leighton:
  Reconstructing a Three-Dimensional Model with Arbitrary Errors. 212-235
  
• Paolo Ferragina, Roberto Grossi:
  The String B-tree: A New Data Structure for String Search in External Memory and Its Applications. 236-280
  
• Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias:
  Provably Efficient Scheduling for Languages with Fine-Grained Parallelism. 281-321
  

Volume 46, Number 3, May 1999

• Fiora Pirri, Raymond Reiter:
  Some Contributions to the Metatheory of the Situation Calculus. 325-361
  
• Mikkel Thorup:
  Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time. 362-394
  
• Gene Myers:
  A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming. 395-415
  
• Fung Yu Young, Chris C. N. Chu, D. F. Wong:
  Generation of Universal Series-Parallel Boolean Functions. 416-435
  

Volume 46, Number 4, July 1999

• Martin Farach, Sampath Kannan:
  Efficient Algorithms for Inverting Evolution. 437-449
  
• Shafi Goldwasser, Joe Kilian:
  Primality Testing Using Elliptic Curves. 450-472
  
• Michael L. Fredman:
  On the Efficiency of Pairing Heaps and Related Data Structures. 473-501
  
• Monika Rauch Henzinger, Valerie King:
  Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. 502-516
  
• Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitányi:
  Mutual Search. 517-536
  
• Saugata Basu:
  New Results on Quantifier Elimination over Real Closed Fields and Applications to Constraint Databases. 537-555
  
• Michael Rodeh, Shmuel Sagiv:
  Finding Circular Attributes in Attribute Grammars. 556
  

Volume 46, Number 5, September 1999

• Jon M. Kleinberg:
  Authoritative Sources in a Hyperlinked Environment. 604-632
  
• Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos:
  Linear Hash Functions. 667-683
  
• Nicolò Cesa-Bianchi, Eli Dichterman, Paul Fischer, Eli Shamir, Hans-Ulrich Simon:
  Sample-Efficient Strategies for Learning in the Presence of Noise. 684-719
  
• Robert D. Blumofe, Charles E. Leiserson:
  Scheduling Multithreaded Computations by Work Stealing. 720-748
  

Volume 46, Number 6, November 1999

• Frank Thomson Leighton, Satish Rao:
  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. 787-832
  
• Yunhong Zhou, Subhash Suri:
  Analysis of a bounding box heuristic for object intersection. 833-857
  
• Maurice Herlihy, Nir Shavit:
  The topological structure of asynchronous computability. 858-923
  
• Rolf H. Möhring, Andreas S. Schulz, Marc Uetz:
  Approximation in stochastic scheduling: the power of LP-based priority policies. 924-942