Theory of Computing Systems, Volume 41

Volume 41, Number 1, July 2007

• S. Barry Cooper, Benedikt Löwe, Peter van Emde Boas:
  Theory of Computation at CiE 2005. 1-2
  Electronic Edition (link) BibTeX
• Jan A. Bergstra, C. A. Middelburg:
  A Thread Algebra with Multi-Level Strategic Interleaving. 3-32
  Electronic Edition (link) BibTeX
• Pieter Collins:
  Optimal Semicomputable Approximations to Reachable and Invariant Sets. 33-48
  Electronic Edition (link) BibTeX
• Amin Farjudian:
  Shrad: A Language for Sequential Real Number Computation. 49-105
  Electronic Edition (link) BibTeX
• Klaus Meer:
  Some Relations between Approximation Problems and PCPs over the Real Numbers. 107-118
  Electronic Edition (link) BibTeX
• Peter Bro Miltersen:
  The Computational Complexity of One-Dimensional Sandpiles. 119-125
  Electronic Edition (link) BibTeX
• Milad Niqui:
  Productivity of Edalat-Potts Exact Arithmetic in Constructive Type Theory. 127-154
  Electronic Edition (link) BibTeX
• Ning Zhong:
  Computable Analysis of a Boundary-Value Problem for the Korteweg-de Vries Equation. 155-175
  Electronic Edition (link) BibTeX
• Martin Ziegler:
  Real Hypercomputation and Continuity. 177-206
  Electronic Edition (link) BibTeX

Volume 41, Number 2, August 2007

• Maciej Liskiewicz, Rüdiger Reischuk:
  Preface. 209-210
  Electronic Edition (link) BibTeX
• Matthias P. Krieger:
  On the Incompressibility of Monotone DNFs. 211-231
  Electronic Edition (link) BibTeX
• Tomasz Jurdzinski, Krzysztof Lorys:
  Leftist Grammars and the Chomsky Hierarchy. 233-256
  Electronic Edition (link) BibTeX
• Daniel Meister:
  Polynomial-Space Decidable Membership Problems for Recurrent Systems over Sets of Natural Numbers. 257-289
  Electronic Edition (link) BibTeX
• Holger Spakowski, Rahul Tripathi:
  On the Power of Unambiguity in Alternating Machines. 291-326
  Electronic Edition (link) BibTeX
• Till Tantau:
  Logspace Optimization Problems and Their Approximability Properties. 327-350
  Electronic Edition (link) BibTeX
• Birgit Schelm:
  Average-Case Non-Approximability of Optimisation Problems. 351-368
  Electronic Edition (link) BibTeX
• Michael Brinkmeier:
  A Simple and Fast Min-Cut Algorithm. 369-380
  Electronic Edition (link) BibTeX
• Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
  Exact Algorithms for Graph Homomorphisms. 381-393
  Electronic Edition (link) BibTeX

Volume 41, Number 3, October 2007

• Rod Downey:
  Foreword. 397
  Electronic Edition (link) BibTeX
• Faisal N. Abu-Khzam:
  Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems. 399-410
  Electronic Edition (link) BibTeX
• Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, W. Henry Suters:
  Crown Structures for Vertex Cover Kernelization. 411-430
  Electronic Edition (link) BibTeX
• Hans-Joachim Böckenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke:
  The Parameterized Approximability of TSP with Deadlines. 431-444
  Electronic Edition (link) BibTeX
• Jonathan F. Buss, Tarique Islam:
  Algorithms in the W-Hierarchy. 445-457
  Electronic Edition (link) BibTeX
• Liming Cai, Michael R. Fellows, David W. Juedes, Frances A. Rosamond:
  The Complexity of Polynomial-Time Approximation. 459-477
  Electronic Edition (link) BibTeX
• Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, Kim Stevens:
  An O(2^O(k)n³) FPT Algorithm for the Undirected Feedback Vertex Set Problem. 479-492
  Electronic Edition (link) BibTeX
• Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, Xinhui Wang:
  Dynamic Programming for Minimum Steiner Trees. 493-500
  Electronic Edition (link) BibTeX
• Jiong Guo, Rolf Niedermeier, Sebastian Wernicke:
  Parameterized Complexity of Vertex Cover Variants. 501-520
  Electronic Edition (link) BibTeX
• Gregory Gutin, Arash Rafiey, Stefan Szeider, Anders Yeo:
  The Linear Arrangement Problem Parameterized Above Guaranteed Value. 521-538
  Electronic Edition (link) BibTeX
• Michael T. Hallett, Catherine McCartin:
  A Faster FPT Algorithm for the Maximum Agreement Forest Problem. 539-550
  Electronic Edition (link) BibTeX
• Petr Hlinený:
  Some Hard Problems on Matroid Spikes. 551-562
  Electronic Edition (link) BibTeX
• Venkatesh Raman, Saket Saurabh, Somnath Sikdar:
  Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. 563-587
  Electronic Edition (link) BibTeX

Volume 41, Number 4, December 2007

• Kunihiko Sadakane:
  Compressed Suffix Trees with Full Functionality. 589-607
  Electronic Edition (link) BibTeX
• F. Cedo, Ana Cortés, Ana Ripoll, Miquel A. Senar, Emilio Luque:
  The Convergence of Realistic Distributed Load-Balancing Algorithms. 609-618
  Electronic Edition (link) BibTeX
• Janis Voigtländer:
  Formal Efficiency Analysis for Tree Transducer Composition. 619-689
  Electronic Edition (link) BibTeX
• Michael Elkin, David Peleg:
  The Hardness of Approximating Spanner Problems. 691-729
  Electronic Edition (link) BibTeX
• Li Gao, Grzegorz Malewicz:
  Toward Maximizing the Quality of Results of Dependent Tasks Computed Unreliably. 731-752
  Electronic Edition (link) BibTeX
• Elmar Böhler, Henning Schnoor:
  The Complexity of the Descriptiveness of Boolean Circuits over Different Sets of Gates. 753-777
  Electronic Edition (link) BibTeX
• Sanjiv Kapoor, Mohammad Sarwat:
  Bounded-Diameter Minimum-Cost Graph Problems. 779-794
  Electronic Edition (link) BibTeX