15. FCT 2005: Lübeck, Germany

Maciej Liskiewicz, Rüdiger Reischuk (Eds.): 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 BibTeX

Invited Talks

Martin Grohe, Christoph Koch, Nicole Schweikardt:
The Complexity of Querying External Memory and Streaming Data. 1-16
Electronic Edition (link) BibTeX
Daniel A. Spielman:
The Smoothed Analysis of Algorithms. 17-18
Electronic Edition (link) BibTeX
Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Path Coupling Using Stopping Times. 19-31
Electronic Edition (link) BibTeX

Matthias P. Krieger:
On the Incompressibility of Monotone DNFs. 32-43
Electronic Edition (link) BibTeX
Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang:
Bounds on the Power of Constant-Depth Quantum Circuits. 44-55
Electronic Edition (link) BibTeX

Daniel Meister:
Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals. 80-91
Electronic Edition (link) BibTeX
Philippe Moser:
Generic Density and Small Span Theorem. 92-102
Electronic Edition (link) BibTeX

Till Tantau:
Logspace Optimization Problems and Their Approximability Properties. 103-114
Electronic Edition (link) BibTeX
Wolfgang W. Bein, Lawrence L. Larmore, Linda Morales, Ivan Hal Sudborough:
A Faster and Simpler 2-Approximation Algorithm for Block Sorting. 115-124
Electronic Edition (link) BibTeX

Holger Spakowski, Rahul Tripathi:
On the Power of Unambiguity in Alternating Machines. 125-136
Electronic Edition (link) BibTeX
Chuzo Iwamoto, Yoshiaki Nakashiba, Kenichi Morita, Katsunobu Imai:
Translational Lemmas for Alternating TMs and PRAMs. 137-148
Electronic Edition (link) BibTeX
Tomoyuki Yamakami:
Collapsing Recursive Oracles for Relativized Polynomial Hierarchies. 149-160
Electronic Edition (link) BibTeX

Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms. 161-171
Electronic Edition (link) BibTeX
Jiong Guo, Rolf Niedermeier, Daniel Raible:
Improved Algorithms and Complexity Results for Power Domination in Graphs. 172-184
Electronic Edition (link) BibTeX
Andreas Brandstädt, Joost Engelfriet, Hoàng-Oanh Le, Vadim V. Lozin:
Clique-Width for Four-Vertex Forbidden Subgraphs. 185-196
Electronic Edition (link) BibTeX

Vincenzo Bonifaci, Ugo Di Iorio, Luigi Laura:
On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems. 197-208
Electronic Edition (link) BibTeX
Bernd Gärtner, Leo Rüst:
Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems. 209-220
Electronic Edition (link) BibTeX

Hans-Ulrich Simon:
Perfect Reconstruction of Black Pixels Revisited. 221-232
Electronic Edition (link) BibTeX
Sheung-Hung Poon, Chan-Su Shin:
Adaptive Zooming in Point Set Labeling. 233-244
Electronic Edition (link) BibTeX

Katalin Friedl, Gábor Ivanyos, Miklos Santha, Yves F. Verhoeven:
On the Black-Box Complexity of Sperner's Lemma. 245-257
Electronic Edition (link) BibTeX
Beate Bollig:
Property Testing and the Branching Program Size of Boolean Functions. 258-269
Electronic Edition (link) BibTeX

Tomasz Jurdzinski, Krzysztof Lorys:
Leftist Grammars and the Chomsky Hierarchy. 293-304
Electronic Edition (link) BibTeX
Markus Holzer, Friedrich Otto:
Shrinking Multi-pushdown Automata. 305-316
Electronic Edition (link) BibTeX

Michael Brinkmeier:
A Simple and Fast Min-cut Algorithm. 317-328
Electronic Edition (link) BibTeX
Eric Angel, Evripidis Bampis, Laurent Gourvès, Jérôme Monnot:
(Non)-Approximability for the Multi-criteria TSP(1, 2). 329-340
Electronic Edition (link) BibTeX

Pawel Waszkiewicz:
Completeness and Compactness of Quantitative Domains. 341-351
Electronic Edition (link) BibTeX
Aleksy Schubert:
A Self-dependency Constraint in the Simply Typed Lambda Calculus. 352-364
Electronic Edition (link) BibTeX
Peeter Laud, Varmo Vene:
A Type System for Computationally Secure Information Flow. 365-377
Electronic Edition (link) BibTeX

Alexander Grigoriev, Hans L. Bodlaender:
Algorithms for Graphs Embeddable with Few Crossings Per Edge. 378-387
Electronic Edition (link) BibTeX
Jérôme Monnot, Sophie Toulouse:
Approximation Results for the Weighted P₄ Partition Problems. 388-396
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX

Birgit Schelm:
Average-Case Non-approximability of Optimisation Problems. 409-421
Electronic Edition (link) BibTeX
Aduri Pavan, N. V. Vinodchandran:
Relations Between Average-Case and Worst-Case Complexity. 422-432
Electronic Edition (link) BibTeX

Joachim Giesen, Dieter Mitsche:
Reconstructing Many Partitions Using Spectral Techniques. 433-444
Electronic Edition (link) BibTeX
Akimitsu Ono, Shin-Ichi Nakano:
Constant Time Generation of Linear Extensions. 445-453
Electronic Edition (link) BibTeX

Sven Köhler, Christian Schindelhauer, Martin Ziegler:
On Approximating Real-World Halting Problems. 454-466
Electronic Edition (link) BibTeX
Klaus Meer, Martin Ziegler:
An Explicit Solution to Post's Problem over the Reals. 467-478
Electronic Edition (link) BibTeX
Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois:
The Complexity of Semilinear Problems in Succinct Representation. 479-490
Electronic Edition (link) BibTeX

Kouichi Hirata, Megumi Kuwabara, Masateru Harao:
On Finding Acyclic Subhypergraphs. 491-503
Electronic Edition (link) BibTeX
Markus Bläser, L. Shankar Ram:
An Improved Approximation Algorithm for TSP with Distances One and Two. 504-515
Electronic Edition (link) BibTeX
Andreas Brandstädt, Van Bang Le, Suhail Mahfud:
New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem. 516-527
Electronic Edition (link) BibTeX

Benedikt Bollig:
On the Expressiveness of Asynchronous Cellular Automata. 528-539
Electronic Edition (link) BibTeX
Julien Bernet, David Janin:
Tree Automata and Discrete Distributed Games. 540-551
Electronic Edition (link) BibTeX

Yo-Sub Han, Derick Wood:
A New Linearizing Restriction in the Pattern Matching Problem. 552-562
Electronic Edition (link) BibTeX
Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda:
Fully Incremental LCS Computation. 563-574
Electronic Edition (link) BibTeX