Journal of the ACM, Volume 49, 2002

Volume 49, Number 1, January 2002

• Lillian Lee:
  Fast context-free grammar parsing requires fast boolean matrix multiplication. 1-15
  
• Seth Pettie, Vijaya Ramachandran:
  An optimal minimum spanning tree algorithm. 16-34
  
• Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas:
  On a model of indexability and its bounds for range queries. 35-55
  
• Frank Neven, Jan Van den Bussche:
  Expressiveness of structured document query languages based on attribute grammars. 56-100
  
• Sibsankar Haldar, Paul M. B. Vitányi:
  Bounded concurrent timestamp systems using vector clocks. 101-126
  

Volume 49, Number 2, March 2002

• Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou:
  Map graphs. 127-138
  
• Rafail Ostrovsky, Yuval Rabani:
  Polynomial-time approximation schemes for geometric min-sum median clustering. 139-156
  
• Ming Li, Bin Ma, Lusheng Wang:
  On the closest string and substring problems. 157-171
  
• Eugene Asarin, Paul Caspi, Oded Maler:
  Timed regular expressions. 172-206
  
• Steven H. Low, Larry L. Peterson, Limin Wang:
  Understanding TCP Vegas: a duality model. 207-235
  
• Tim Roughgarden, Éva Tardos:
  How bad is selfish routing? 236-259
  
• Mor Harchol-Balter:
  Task assignment with unknown duration. 260-288
  

Volume 49, Number 3, May 2002

• Uri Zwick:
  All pairs shortest paths using bridging sets and rectangular matrix multiplication. 289-317
  
• Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer:
  Compactly encoding unstructured inputs with differential compression. 318-367
  
• Wenfei Fan, Leonid Libkin:
  On XML integrity constraints in the presence of DTDs. 368-406
  
• Hisao Kameda, Odile Pourtallier:
  Paradoxes in distributed decisions on optimal load balancing for networks of homogeneous computers. 407-433
  
• Michael A. Frumkin, Rob F. Van der Wijngaart:
  Tight bounds on cache use for stencil operations on rectangular grids. 434-453
  

Volume 49, Number 4, July 2002

• Didier Dubois, Hélène Fargier, Henri Prade, Patrice Perny:
  Qualitative decision theory: from savage's axioms to nonmonotonic reasoning. 455-495
  
• Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani:
  Dense quantum coding and quantum finite automata. 496-511
  
• David A. McAllester:
  On the complexity analysis of static analyses. 512-537
  
• Karthikeyan Bhargavan, Davor Obradovic, Carl A. Gunter:
  Formal verification of standards for distance vector routing protocols. 538-576
  

Volume 49, Number 5, September 2002

• Daniel J. Lehmann, Liadan O'Callaghan, Yoav Shoham:
  Truth revelation in approximately efficient combinatorial auctions. 577-602
  
• Daniel H. Huson, Knut Reinert, Eugene W. Myers:
  The greedy path-merging algorithm for contig scaffolding. 603-615
  
• Jon M. Kleinberg, Éva Tardos:
  Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. 616-639
  
• Steven S. Seiden:
  On the online bin packing problem. 640-671
  
• Rajeev Alur, Thomas A. Henzinger, Orna Kupferman:
  Alternating-time temporal logic. 672-713
  

Volume 49, Number 6, November 2002

• Joseph Y. Halpern:
  Update: Time to publication statistics. 715
  
• Jörg Flum, Markus Frick, Martin Grohe:
  Query evaluation via tree-decompositions. 716-752
  
• Larry J. Stockmeyer, Albert R. Meyer:
  Cosmological lower bound on the circuit complexity of a small problem in logic. 753-784
  
• Gilbert Caplain:
  Correctness properties in a shared-memory parallel language. 785-827
  
• Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir:
  Towards a theory of cache-efficient algorithms. 828-858