Theoretical Computer Science, Volume 385

Volume 385, Numbers 1-3, October 2007

• Xueliang Li, Xiaoyan Zhang:
  On the minimum monochromatic or multicolored subgraph partition problems. 1-10
  
• Yves Andre, Anne-Cécile Caron, Denis Debarbieux, Yves Roos, Sophie Tison:
  Path constraints in semistructured data. 11-33
  
• Shantanu Das, Paola Flocchini, Shay Kutten, Amiya Nayak, Nicola Santoro:
  Map construction of unknown graphs by multiple agents. 34-48
  
• My T. Thai, Ning Zhang, Ravi Tiwari, Xiaochun Xu:
  On approximation algorithms of k-connected m-dominating sets in disk graphs. 49-59
  
• Hajo Broersma, Xueliang Li:
  On the complexity of dominating set problems related to the minimum all-ones problem. 60-70
  
• Weifan Wang, Yongzhu Chen:
  A sufficient condition for a planar graph to be class 1. 71-77
  
• Giulia Galbiati, Francesco Maffioli:
  Approximation algorithms for maximum cut with limited unbalance. 78-87
  
• Ming Yu Hsieh, Shi-Chun Tsai:
  On the fairness and complexity of generalized k-in-a-row games. 88-100
  
• Maleq Khan, Gopal Pandurangan, V. S. Anil Kumar:
  A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms. 101-114
  
• V. Y. Popov:
  Multiple genome rearrangement by swaps and by element duplications. 115-126
  
• Joong Chae Na, Kunsoo Park:
  Alphabet-independent linear-time construction of compressed suffix arrays using o(nlogn)-bit working space. 127-136
  
• Arturo Carpi:
  On Dejean's conjecture over large alphabets. 137-151
  
• Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi, Antonio Restivo, Marinella Sciortino:
  Languages with mismatches. 152-166
  
• Aduri Pavan, Alan L. Selman, Samik Sengupta, N. V. Vinodchandran:
  Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. 167-178
  
• Francine Blanchet-Sadri, Nathan D. Wetzler:
  Partial words and the critical factorization theorem revisited. 179-192
  
• Verónica Becher, Serge Grigorieff:
  Random reals à la Chaitin with or without prefix-freeness. 193-201
  
• André Berger, Takuro Fukunaga, Hiroshi Nagamochi, Ojas Parekh:
  Approximability of the capacitated b-edge dominating set problem. 202-213
  
• Nicolas Bedaride:
  Classification of rotations on the torus T². 214-225
  
• Dieter Kratsch, Mathieu Liedloff:
  An exact algorithm for the minimum dominating clique problem. 226-240
  
• Guillaume Blin, Guillaume Fertin, Stéphane Vialette:
  Extracting constrained 2-interval subsets in 2-interval sets. 241-263
  
• Francesco M. Malvestuto, Mauro Mezzini, Marina Moscarini:
  An analytical approach to the inference of summary data of additive type. 264-285
  
• Jywe-Fei Fang:
  The bipanconnectivity and m-panconnectivity of the folded hypercube. 286-300