Theory of Computing Systems, Volume 39

Volume 39, Number 1, February 2006

• Volker Diekert, Michel Habib:
  Foreword. 1
  
• Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki:
  Matching Algorithms Are Fast in Sparse Random Graphs. 3-14
  
• Daniel Kirsten:
  A Burnside Approach to the Finite Substitution Problem. 15-50
  
• Torsten Tholey:
  Solving the 2-Disjoint Paths Problem in Nearly Linear Time. 51-78
  
• Kristoffer Arnsfelt Hansen:
  Constant Width Planar Computation Characterizes ACC⁰. 79-92
  
• Kedar Dhamdhere, Anupam Gupta, R. Ravi:
  Approximation Algorithms for Minimizing Average Distortion. 93-111
  
• Torben Hagerup:
  Simpler Computation of Single-Source Shortest Paths in Linear Average Time. 113-120
  
• Alexander Souza, Angelika Steger:
  The Expected Competitive Ratio for Weighted Completion Time Scheduling. 121-136
  
• Sebastian Bala:
  Complexity of Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints Between Regular Open Terms. 137-163
  
• Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien:
  Algebraic Results on Quantum Automata. 165-188
  
• Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek:
  Time-Space Tradeoff in Derandomizing Probabilistic Logspace. 189-208
  
• Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati:
  Local Limit Properties for Pattern Statistics and Rational Models. 209-235
  
• Anca Muscholl, Thomas Schwentick, Luc Segoufin:
  Active Context-Free Games. 237-276
  

Volume 39, Number 2, April 2006

• John M. Hitchcock, Jack H. Lutz:
  Why Computational Complexity Requires Stricter Martingales. 277-296
  
• Étienne Ailloud, Arnaud Durand:
  The Expressive Power of Bijections over Weakly Arithmetized Structures. 297-309
  
• Xiaoyu Song, Guowu Yang, Marek A. Perkowski, Yuke Wang:
  Algebraic Characterization of Reversible Logic Gates. 311-319
  
• Gianni Franceschini, Roberto Grossi:
  Optimal Implicit Dictionaries over Unbounded Universes. 321-345
  
• Christof Löding:
  Reachability Problems on Regular Ground Tree Rewriting Graphs. 347-383
  
• Xizhong Zheng, Robert Rettinger:
  A Reference Correction of "Effective Jordan Decomposition". 385-385
  

Volume 39, Number 3, June 2006

• Paolo Ferragina, Roberto Grossi, Fabrizio Luccio:
  Foreword. 389
  
• Michael A. Bender, Martin Farach-Colton, Miguel A. Mosteiro:
  Insertion Sort is O(n log n). 391-397
  
• Navin Goyal, Sachin Lodha, S. Muthukrishnan:
  The Graham-Knowlton Problem Revisited. 399-412
  
• Frank Ruskey, Mark Weston:
  More Fun with Symmetric Venn Diagrams. 413-423
  
• Jean Cardinal, Steve Kremer, Stefan Langerman:
  Juggling with Pattern Matching. 425-437
  
• Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman:
  Morpion Solitaire. 439-453
  
• Sebastian Böcker:
  Sequencing from Compomers: The Puzzle. 455-471
  
• Erik D. Demaine, Martin L. Demaine:
  Puzzles, Art, and Magic with Algorithms. 473-481
  

Volume 39, Number 4, July 2006

• Anna Bernasconi, Valentina Ciriani, Fabrizio Luccio, Linda Pagli:
  Exploiting Regularities for Boolean Function Synthesis. 485-501
  
• Paolo Bottoni, Anna Labella, Vincenzo Manca, Victor Mitrana:
  Superposition Based on Watson-Crick-Like Complementarity. 503-524
  
• Stefan Droste, Thomas Jansen, Ingo Wegener:
  Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization. 525-544
  
• Jens Gramm, Jiong Guo, Rolf Niedermeier:
  Parameterized Intractability of Distinguishing Substring Selection. 545-560
  
• Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin:
  Clique-Width for 4-Vertex Forbidden Subgraphs. 561-590
  

Volume 39, Number 5, September 2006

• Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
  Energy-Efficient Wireless Network Design. 593-617
  
• Mark Daley, Ian McQuillan:
  Useful Templates and Iterated Template-Guided DNA Recombination in Ciliates. 619-633
  
• Tobias Riege, Jörg Rothe:
  Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem. 635-668
  
• Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed J. Zaki, Marius Zimand:
  The Complexity of Finding Top-Toda-Equivalence-Class Members. 669-684
  
• Wolfgang Merkle, Jan Reimann:
  Selection Functions that Do Not Preserve Normality. 685-697
  
• Howard Straubing, Denis Thérien:
  A Note on MOD_p - MOD_m Circuits. 699-706
  
• Wolfgang Merkle, Nenad Mihailovic, Theodore A. Slaman:
  Some Results on Effective Randomness. 707-721
  
• Masaki Yamamoto:
  Generating Instances for MAX2SAT with Optimal Solutions. 723-742
  
• Bruce E. Litow:
  A Special Case of a Unary Regular Language Containment. 743-751
  
• Richard Gault, Iain A. Stewart:
  An Infinite Hierarchy in a Class of Polynomial-Time Program Schemes. 753-783
  

Volume 39, Number 6, November 2006

• Peter Sanders, Aravind Srinivasan, Berthold Vöcking:
  Foreword. 785
  
• David R. Karger, Matthias Ruhl:
  Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems. 787-804
  
• Adi Rosén, Michael S. Tsirkin:
  On Delivery Times in Packet Networks under Adversarial Traffic. 805-827
  
• Fan R. K. Chung, Ronald L. Graham, Jia Mao, George Varghese:
  Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines. 829-849
  
• Xiaozhou Li, C. Greg Plaxton, Mitul Tiwari, Arun Venkataramani:
  Online Hierarchical Cooperative Caching. 851-874
  
• Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura, Roger Wattenhofer:
  Dynamic Analysis of the Arrow Distributed Protocol. 875-901
  
• Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler:
  The Effect of Faults on Network Expansion. 903-928
  
• Konstantin Andreev, Harald Räcke:
  Balanced Graph Partitioning. 929-939