Skip to main content
SpringerLink
Log in

Fundamentals of Computation Theory

15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings

  • Conference proceedings
  • © 2005

Overview

Editors:
  1. Maciej Liśkiewicz

    1. Institut für Theoretische Informatik, Universität zu Lübeck, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rüdiger Reischuk

    1. Institut für Theoretische Informatik, Universität zu Lübeck, Lübeck, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 3623)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: FCT 2005.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (49 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Talks

    1. The Complexity of Querying External Memory and Streaming Data

      • Martin Grohe, Christoph Koch, Nicole Schweikardt
      Pages 1-16

    2. The Smoothed Analysis of Algorithms

      • Daniel A. Spielman
      Pages 17-18

    3. Path Coupling Using Stopping Times

      • Magnus Bordewich, Martin Dyer, Marek Karpinski
      Pages 19-31

  3. Circuits

    1. On the Incompressibility of Monotone DNFs

      • Matthias P. Krieger
      Pages 32-43

    2. Bounds on the Power of Constant-Depth Quantum Circuits

      • Stephen Fenner, Frederic Green, Steven Homer, Yong Zhang
      Pages 44-55

  4. Automata I

    1. Biautomatic Semigroups

      • Michael Hoffmann, Richard M. Thomas
      Pages 56-67

    2. Deterministic Automata on Unranked Trees

      • Julien Cristau, Christof Löding, Wolfgang Thomas
      Pages 68-79

  6. Approximability

    1. Logspace Optimization Problems and Their Approximability Properties

      • Till Tantau
      Pages 103-114

    2. A Faster and Simpler 2-Approximation Algorithm for Block Sorting

      • Wolfgang W. Bein, Lawrence L. Larmore, Linda Morales, I. Hal Sudborough
      Pages 115-124

  7. Computational and Structural Complexity

    1. On the Power of Unambiguity in Alternating Machines

      • Holger Spakowski, Rahul Tripathi
      Pages 125-136

    2. Translational Lemmas for Alternating TMs and PRAMs

      • Chuzo Iwamoto, Yoshiaki Nakashiba, Kenichi Morita, Katsunobu Imai
      Pages 137-148

    3. Collapsing Recursive Oracles for Relativized Polynomial Hierarchies

      • Tomoyuki Yamakami
      Pages 149-160

  8. Graphs and Complexity

    1. Exact Algorithms for Graph Homomorphisms

      • Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch
      Pages 161-171

    2. Improved Algorithms and Complexity Results for Power Domination in Graphs

      • Jiong Guo, Rolf Niedermeier, Daniel Raible
      Pages 172-184

    3. Clique-Width for Four-Vertex Forbidden Subgraphs

      • Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin
      Pages 185-196

  9. Computational Game Theory

    1. On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems

      • Vincenzo Bonifaci, Ugo Di Iorio, Luigi Laura
      Pages 197-208

    2. Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems

      • Bernd Gärtner, Leo Rüst
      Pages 209-220
Back to top

Other volumes

  1. Fundamentals of Computation Theory

Keywords

Editors and Affiliations

  • Institut für Theoretische Informatik, Universität zu Lübeck, Germany

    Maciej Liśkiewicz

  • Institut für Theoretische Informatik, Universität zu Lübeck, Lübeck, Germany

    Rüdiger Reischuk

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation