default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID15th FCT 2005: Lübeck, Germany
- Maciej Liskiewicz, Rüdiger Reischuk:
Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings. Lecture Notes in Computer Science 3623, Springer 2005, ISBN 3-540-28193-2
Invited Talks
- Martin Grohe, Christoph Koch, Nicole Schweikardt:
The Complexity of Querying External Memory and Streaming Data. 1-16 - Daniel A. Spielman:
The Smoothed Analysis of Algorithms. 17-18 - Magnus Bordewich
, Martin E. Dyer, Marek Karpinski:
Path Coupling Using Stopping Times. 19-31
Circuits
- Matthias P. Krieger:
On the Incompressibility of Monotone DNFs. 32-43 - Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang:
Bounds on the Power of Constant-Depth Quantum Circuits. 44-55
Automata I
- Michael Hoffmann, Richard M. Thomas:
Biautomatic Semigroups. 56-67 - Julien Cristau, Christof Löding, Wolfgang Thomas:
Deterministic Automata on Unranked Trees. 68-79
Complexity I
- Daniel Meister:
Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals. 80-91 - Philippe Moser:
Generic Density and Small Span Theorem. 92-102
Approximability
- Till Tantau:
Logspace Optimization Problems and Their Approximability Properties. 103-114 - Wolfgang W. Bein, Lawrence L. Larmore, Linda Morales, Ivan Hal Sudborough:
A Faster and Simpler 2-Approximation Algorithm for Block Sorting. 115-124
Computational and Structural Complexity
- Holger Spakowski, Rahul Tripathi:
On the Power of Unambiguity in Alternating Machines. 125-136 - Chuzo Iwamoto, Yoshiaki Nakashiba, Kenichi Morita, Katsunobu Imai:
Translational Lemmas for Alternating TMs and PRAMs. 137-148 - Tomoyuki Yamakami:
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies. 149-160
Graphs and Complexity
- Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms. 161-171 - Jiong Guo, Rolf Niedermeier, Daniel Raible:
Improved Algorithms and Complexity Results for Power Domination in Graphs. 172-184 - Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin:
Clique-Width for Four-Vertex Forbidden Subgraphs. 185-196
Computational Game Theory
- Vincenzo Bonifaci, Ugo Di Iorio, Luigi Laura:
On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems. 197-208 - Bernd Gärtner, Leo Rüst:
Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems. 209-220
Visual Cryptography and Computational Geometry
- Hans Ulrich Simon:
Perfect Reconstruction of Black Pixels Revisited. 221-232 - Sheung-Hung Poon, Chan-Su Shin:
Adaptive Zooming in Point Set Labeling. 233-244
Query Complexity
- Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven:
On the Black-Box Complexity of Sperner's Lemma. 245-257 - Beate Bollig:
Property Testing and the Branching Program Size of Boolean Functions. 258-269
Distributed Systems
- Bogdan S. Chlebus, Dariusz R. Kowalski:
Almost Optimal Explicit Selectors. 270-280 - Wolfgang W. Bein, Kazuo Iwama, Lawrence L. Larmore, John Noga:
The Delayed k-Server Problem. 281-292
Automata and Formal Languages
- Tomasz Jurdzinski, Krzysztof Lorys:
Leftist Grammars and the Chomsky Hierarchy. 293-304 - Markus Holzer, Friedrich Otto:
Shrinking Multi-pushdown Automata. 305-316
Graph Algorithms
- Michael Brinkmeier:
A Simple and Fast Min-cut Algorithm. 317-328 - Eric Angel, Evripidis Bampis, Laurent Gourvès, Jérôme Monnot:
(Non)-Approximability for the Multi-criteria TSP(1, 2). 329-340
Semantics
- Pawel Waszkiewicz:
Completeness and Compactness of Quantitative Domains. 341-351 - Aleksy Schubert:
A Self-dependency Constraint in the Simply Typed Lambda Calculus. 352-364 - Peeter Laud, Varmo Vene:
A Type System for Computationally Secure Information Flow. 365-377
Approximation Algorithms
- Alexander Grigoriev, Hans L. Bodlaender:
Algorithms for Graphs Embeddable with Few Crossings Per Edge. 378-387 - Jérôme Monnot, Sophie Toulouse:
Approximation Results for the Weighted P4 Partition Problems. 388-396 - Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, Sanne Wøhlk:
The Maximum Resource Bin Packing Problem. 397-408
Average-Case Complexity
- Birgit Schelm:
Average-Case Non-approximability of Optimisation Problems. 409-421 - Aduri Pavan, N. V. Vinodchandran:
Relations Between Average-Case and Worst-Case Complexity. 422-432
Algorithms
- Joachim Giesen, Dieter Mitsche:
Reconstructing Many Partitions Using Spectral Techniques. 433-444 - Akimitsu Ono, Shin-Ichi Nakano:
Constant Time Generation of Linear Extensions. 445-453
Complexity II
- Sven Köhler, Christian Schindelhauer, Martin Ziegler:
On Approximating Real-World Halting Problems. 454-466 - Klaus Meer, Martin Ziegler:
An Explicit Solution to Post's Problem over the Reals. 467-478 - Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois:
The Complexity of Semilinear Problems in Succinct Representation. 479-490
Graph Algorithms
- Kouichi Hirata, Megumi Kuwabara, Masateru Harao:
On Finding Acyclic Subhypergraphs. 491-503 - Markus Bläser, L. Shankar Ram:
An Improved Approximation Algorithm for TSP with Distances One and Two. 504-515 - Andreas Brandstädt, Van Bang Le, Suhail Mahfud:
New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem. 516-527
Automata II
- Benedikt Bollig:
On the Expressiveness of Asynchronous Cellular Automata. 528-539 - Julien Bernet, David Janin:
Tree Automata and Discrete Distributed Games. 540-551
Pattern Matching
- Yo-Sub Han, Derick Wood:
A New Linearizing Restriction in the Pattern Matching Problem. 552-562 - Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda:
Fully Incremental LCS Computation. 563-574
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-01-29 02:08 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
