Theoretical Computer Science, Volume 209

Volume 209, Numbers 1-2, 6 December 1998

• Hans L. Bodlaender:
  A Partial k-Arboretum of Graphs with Bounded Treewidth. 1-45
  
• Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay:
  Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. 47-86
  
• Philippe Béguin, Antonella Cresti:
  General Information Dispersal Algorithms. 87-105
  
• Marc Demange, Pascal Grisoni, Vangelis Th. Paschos:
  Differential Approximation Algorithms for Some Combinatorial Optimization Problems. 107-122
  
• Rodney G. Downey, Michael R. Fellows:
  Threshold Dominating Sets and an Improved Characterization of W[2]. 123-140
  
• Bruno Apolloni, Claudio Gentile:
  Sample Size Lower Bounds in PAC Learning by Algorithmic Complexity Theory. 141-162
  
• Luca Aceto, Wan Fokkink, Anna Ingólfsdóttir:
  On a Question of A. Salomaa: The Equational Theory of Regular Expressions Over a Singleton Alphabet is not Finitely Based. 163-178
  
• François Blanchard, Petr Kurka:
  Language Complexity of Rotations and Sturmian Sequences. 179-193
  
• Luisa Gargano, Adele A. Rescigno:
  Communication Complexity of Fault-Tolerant Information Diffusion. 195-211
  
• Erzsébet Csuhaj-Varjú, Alica Kelemenová:
  Team Behaviour in Eco-Grammar Systems. 213-224
  
• Marius Zimand:
  On the Size of Classes with Weak Membership Properties. 225-235
  
• Edoardo Amaldi, Viggo Kann:
  On the Approximability of Minimizing Nonzero Variables or Unsatisfied Relations in Linear Systems. 237-260
  
• Laurent Vuillon:
  Combinatoire des motifs d'une suite sturmienne bidimensionnelle. 261-285
  
• Carsten Rössner, Jean-Pierre Seifert:
  On the Hardness of Approximating Shortest Integer Relations among Rational Numbers. 287-297
  
• Martin Beaudry:
  Languages Recognized by Finite Aperiodic Groupoids. 299-317
  
• György Vaszil:
  On Simulating Non-Returning PC Grammar Systems with Returning Systems. 319-329
  
• Charles J. Colbourn, Guoliang Xue:
  A Linear Time Algorithm for Computing the Most Reliable Source on a Series-Parallel Graph with Unreliable Edges. 331-345
  
• Ewa Malesinska, Alessandro Panconesi:
  On the Hardness of Allocating Frequences for Hybrid Networks. 347-363
  
• Dany Breslauer:
  On Competitive On-Line Paging with Lookahead. 365-375
  
• T. Downarowicz, Y. Lacroix:
  Merit Factors and Morse Sequences. 377-387
  
• Rimli Sengupta, H. Venkateswaran:
  A Lower Bound for Monotone Arithmetic Circuits Computing 0-1 Permanent. 389-398