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

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