15. FCT 2005: Lübeck, Germany

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 P₄ 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
  

Last update Fri May 25 08:14:02 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page