Theory of Computing Systems, Volume 42

Volume 42, Number 1, January 2008

• Paul G. Spirakis:
  Preface. 1
  
• Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Joseph Naor, Baruch Schieber:
  Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees. 2-26
  
• Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir, Mark R. Tuttle:
  Collaborate with Strangers to Find Own Preferences. 27-41
  
• Ioannis Chatzigiannakis, Athanasios Kinalis, Sotiris E. Nikoletseas:
  Adaptive Energy Management for Incremental Deployment of Heterogeneous Wireless Sensors. 42-72
  
• Piotr Sankowski:
  Processor Efficient Parallel Matching. 73-90
  
• Martin Gairing, Burkhard Monien, Karsten Tiemann:
  Selfish Routing with Incomplete Information. 91-130
  

Volume 42, Number 2, February 2008

• John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran:
  Partial Bi-immunity, Scaled Dimension, and NP-Completeness. 131-142
  
• Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, Takeaki Uno:
  A Generalization of Magic Squares with Applications to Digital Halftoning. 143-156
  
• Christian Wartena:
  Storage Products and Linear Control of Derivations. 157-186
  
• Koichi Koizumi, Takaaki Mizuki, Takao Nishizeki:
  A Revised Transformation Protocol for Unconditionally Secure Secret Key Exchange. 187-221
  
• Michael Okun, Amnon Barak:
  Efficient Algorithms for Anonymous Byzantine Agreement. 222-238
  
• Nadia Creignou, Miki Hermann, Andrei A. Krokhin, Gernot Salzer:
  Complexity of Clausal Constraints Over Chains. 239-255
  
• Christian Glaßer, Heinz Schmitz:
  Languages of Dot-Depth 3/2. 256-286
  

Volume 42, Number 3, April 2008

• Mario Coppo, Elena Lodi, G. Michele Pinna:
  Foreword. 287-288
  
• Yuichi Asahiro, Eiji Miyano, Shinichi Shimoirisa:
  Grasp and Delivery for Moving Objects on Broken Lines. 289-305
  
• Steffen van Bakel, Ugo de'Liguoro:
  Logical Equivalence for Subtyping Object and Recursive Types. 306-348
  
• Tsvi Kopelowitz, Ely Porat:
  Improved Algorithms for Polynomial-Time Decay and Time-Decay with Additive Error. 349-365
  
• Wojciech Jamroga, Jürgen Dix:
  Model Checking Abilities of Agents: A Closer Look. 366-410
  
• Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino:
  A New Combinatorial Approach to Sequence Comparison. 411-429
  

Volume 42, Number 4, May 2008

• Leah Epstein, Arik Ganot:
  Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation. 431-449
  
• Anna Bernasconi, Valentina Ciriani, Fabrizio Luccio, Linda Pagli:
  Synthesis of Autosymmetric Functions in a New Three-Level Form. 450-464
  
• Micah Adler, Ying Gong, Arnold L. Rosenberg:
  On "Exploiting" Node-Heterogeneous Clusters Optimally. 465-487
  
• Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek:
  On the Complexity of 2-Monotone Restarting Automata. 488-518
  
• Kieran T. Herley, Andrea Pietracaprina, Geppino Pucci:
  Store-and-Forward Multicast Routing on the Mesh. 519-535
  
• Blaise Genest, Anca Muscholl:
  Pattern Matching and Membership for Hierarchical Message Sequence Charts. 536-567
  
• José L. Balcázar, Yang Dai, Junichi Tanaka, Osamu Watanabe:
  Provably Fast Training Algorithms for Support Vector Machines. 568-595
  
• Aduri Pavan, N. V. Vinodchandran:
  Relations between Average-Case and Worst-Case Complexity. 596-607
  
• Manfred Droste, Paul Gastin:
  On Aperiodic and Star-Free Formal Power Series in Partially Commuting Variables. 608-631
  
• Michele Flammini, Luca Moscardelli, Alfredo Navarra, Stéphane Pérennes:
  Asymptotically Optimal Solutions for Small World Graphs. 632-650