Theoretical Computer Science, Volume 407

Volume 407, Numbers 1-3, November 2008

• Stefan Eckhardt, Sven Kosub, Moritz G. Maaß, Hanjo Täubig, Sebastian Wernicke:
  Combinatorial network abstraction by trees and distances. 1-20
  
• Junlei Zhu, Yuehua Bu:
  Equitable list colorings of planar graphs without short cycles. 21-28
  
• Maurice Margenstern:
  The domino problem of the hyperbolic plane is undecidable. 29-84
  
• Leah Epstein, Asaf Levin, Rob van Stee:
  Online unit clustering: Variations on a theme. 85-96
  
• Hervé Fournier, Guillaume Malod:
  Universal relations and #P-completeness. 97-109
  
• Meijie Ma, Guizhen Liu, Jun-Ming Xu:
  Fault-tolerant embedding of paths in crossed cubes. 110-116
  
• Marion Le Gonidec:
  On complexity functions of infinite words associated with generalized Dyck languages. 117-133
  
• Charilaos Efthymiou, Paul G. Spirakis:
  Random sampling of colourings of sparse random graphs with a constant number of colours. 134-154
  
• Alin Bostan, Claude-Pierre Jeannerod, Éric Schost:
  Solving structured linear systems with large displacement rank. 155-181
  
• Tian-Ming Bu, Xiaotie Deng, Qi Qi:
  Arbitrage opportunities across sponsored search markets. 182-191
  
• Pedro García, Manuel Vazquez de Parga, Gloria I. Álvarez, José Ruiz:
  Universal automata and NFA learning. 192-202
  
• Leah Epstein, Meital Levy:
  Online interval coloring with packing constraints. 203-212
  
• Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci:
  New constructions for provably-secure time-bound hierarchical key assignment schemes. 213-230
  
• Sven Oliver Krumke, Willem de Paepe, Jörg Rambau, Leen Stougie:
  Bincoloring. 231-241
  
• Andrew Beveridge, Tom Bohman, Alan M. Frieze, Oleg Pikhurko:
  Game chromatic index of graphs with given restrictions on degrees. 242-249
  
• Arto Salomaa:
  Subword histories and associated matrices. 250-257
  
• Jonathan K. Lee, Jens Palsberg, Fernando Magno Quintão Pereira:
  Aliased register allocation for straight-line programs is NP-complete. 258-273
  
• Marco Chiarandini, Ilias S. Kotsireas, Christos Koukouvinos, Luis Paquete:
  Heuristic algorithms for Hadamard matrices with two circulant cores. 274-277
  
• Ondrej Klíma, Libor Polák:
  On varieties of meet automata. 278-289
  
• Élise Prieur, Thierry Lecroq:
  On-line construction of compact suffix vectors and maximal repeats. 290-301
  
• Adam L. Buchsbaum, Raffaele Giancarlo, Balázs Rácz:
  New results for finding common neighborhoods in massive graphs in the data stream model. 302-309
  
• Jiang Chen, Ke Yi:
  A dynamic data structure for top-k queries on uncertain data. 310-317
  
• Jung-Sheng Fu:
  Fault-free Hamiltonian cycles in twisted cubes with conditional link faults. 318-329
  
• Marcin Kozik:
  A finite set of functions with an EXPTIME-complete composition problem. 330-341
  
• Carlos Alberto Alonso Sanches, Nei Yoshihiro Soma, Horacio Hideki Yanasse:
  Parallel time and space upper-bounds for the subset-sum problem. 342-348
  
• Hsiao-Fei Liu, Kun-Mao Chao:
  Algorithms for finding the weight-constrained k longest paths in a tree and the length-constrained k maximum-sum segments of a sequence. 349-358
  
• Elitza N. Maneva, Alistair Sinclair:
  On the satisfiability threshold and clustering of solutions of random 3-SAT formulas. 359-369
  
• Guomin Yang, Jing Chen, Duncan S. Wong, Xiaotie Deng, Dongsheng Wang:
  A new framework for the design and analysis of identity-based identification schemes. 370-388
  
• Rongjun Chen, Wanzhen Huang, Guochun Tang:
  Dense open-shop schedules with release times. 389-399
  
• Katherine P. Benedetto, Nicholas A. Loehr:
  Tiling problems, automata, and tiling graphs. 400-411
  
• Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer:
  Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. 412-447
  
• Hans Kleine Büning, Xishun Zhao:
  Computational complexity of quantified Boolean formulas with fixed maximal deficiency. 448-457
  
• Matthieu Latapy:
  Main-memory triangle computations for very large (sparse (power-law)) graphs. 458-473
  
• Kei Uchizawa, Eiji Takimoto:
  Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity. 474-487
  
• J. Balogh, Sergei L. Bezrukov, L. H. Harper, Ákos Seress:
  On the bandwidth of 3-dimensional Hamming graphs. 488-495
  
• Qianchuan Zhao, Jianfeng Mao, Tao Ye:
  Time separations of cyclic event rule systems with min-max timing constraints. 496-510
  
• Scott C.-H. Huang, F. Frances Yao, Minming Li, Weili Wu:
  Lower bounds and new constructions on secure group communication schemes. 511-523
  
• Hung-Lung Wang, Kun-Mao Chao:
  The 2-radius and 2-radiian problems on trees. 524-531
  
• Boting Yang, Yi Cao:
  Monotonicity in digraph search problems. 532-544
  
• Hong-Yiu Lin, Yuh-Dauh Lyuu, Tak-Man Ma, Yen-Wu Ti:
  Testing whether a digraph contains H-free k-induced subgraphs. 545-553
  
• Jin-Ju Hong, Gen-Huey Chen:
  Efficient on-line repetition detection. 554-563
  

• Frédéric Cazals, Chinmay Karande:
  A note on the problem of reporting maximal cliques. 564-568
  
• Aldo de Luca, Amy Glen, Luca Q. Zamboni:
  Rich, Sturmian, and trapezoidal words. 569-573
  
• Mieczyslaw Borowiecki, Katarzyna Jesse-Józefczyk:
  Matching cutsets in graphs of diameter 2. 574-582
  
• Ye Du:
  On the complexity of deciding bimatrix games similarity. 583-586
  
• Benny Porat, Ely Porat, Asaf Zur:
  Pattern matching with pair correlation distance. 587-590
  
• Gábor Horváth, Chrystopher L. Nehaniv, Csaba Szabó:
  An assertion concerning functionally complete algebras and NP-completeness. 591-595
  
• Eero Lehtonen:
  Two undecidable variants of Collatz's problems. 596-600