30. MFCS 2005: Gdansk, Poland

Invited Lectures

• Marcin Bienkowski, Friedhelm Meyer auf der Heide:
  Page Migration in Dynamic Networks. 1-14
  
• Rusins Freivalds:
  Knot Theory, Jones Polynomial and Quantum Computing. 15-25
  
• Yuri Gurevich:
  Interactive Algorithms 2005. 26-38
  
• Oscar H. Ibarra:
  Some Computational Issues in Membrane Computing. 39-51
  
• Endre Szemerédi, Andrzej Rucinski, Vojtech Rödl:
  The Generalization of Dirac's Theorem for Hypergraphs. 52-56
  
• Andrew Chi-Chih Yao:
  On the Communication Complexity of Co-linearity Problems. 57
  
• Wieslaw Zielonka:
  An Invitation to Play. 58-70
  

Papers

• Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer:
  The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. 71-82
  
• César Luis Alonso, José Luis Montaña, Luis Miguel Pardo:
  On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions. 83-94
  
• Carme Àlvarez, Joaquim Gabarró, Maria J. Serna:
  Pure Nash Equilibria in Games with a Large Number of Actions. 95-106
  
• Kazuyuki Amano, Akira Maruoka:
  On the Complexity of Depth-2 Circuits with Threshold Gates. 107-118
  
• Michael Bauland, Edith Hemaspaandra:
  Isomorphic Implication. 119-130
  
• Valérie Berthé, Michel Rigo:
  Abstract Numeration Systems and Tilings. 131-143
  
• Maria J. Blesa, Daniel Calzada, Antonio Fernández, Luis López, Andrés L. Martínez, Agustín Santos, Maria J. Serna:
  Adversarial Queueing Model for Continuous Network Dynamics. 144-155
  
• Julia Böttcher:
  Coloring Sparse Random k-Colorable Graphs in Polynomial Expected Time. 156-167
  
• Arnaud Carayol:
  Regular Sets of Higher-Order Pushdown Stacks. 168-179
  
• Arnaud Carayol, Antoine Meyer:
  Linearly Bounded Infinite Graphs. 180-191
  
• Julien Cervelle, Enrico Formenti, Benoît Masson:
  Basic Properties for Sand Automata. 192-211
  
• Jérémie Chalopin, Yves Métivier:
  A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs. 212-223
  
• Ho-Leung Chan, Jesper Jansson, Tak Wah Lam, Siu-Ming Yiu:
  Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. 224-235
  
• Wun-Tat Chan, Tak Wah Lam, Kin-Shing Liu, Prudence W. H. Wong:
  New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling. 236-247
  
• Ho-Lun Cheng, Tony Tan:
  Approximating Polygonal Objects by Deformable Smooth Surfaces. 248-259
  
• Dimitri Chubarov, Andrei Voronkov:
  Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications. 260-270
  
• Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro:
  Asynchronous Deterministic Rendezvous in Graphs. 271-282
  
• David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, Philippe Moser:
  Zeta-Dimension. 283-294
  
• Leah Epstein, Meital Levy:
  Online Interval Coloring with Packing Constraints. 295-307
  
• Piotr Faliszewski, Mitsunori Ogihara:
  Separating the Notions of Self- and Autoreducibility. 308-315
  
• Nazim Fatès, Michel Morvan, Nicolas Schabanel, Eric Thierry:
  Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. 316-327
  
• Guillaume Fertin, Romeo Rizzi, Stéphane Vialette:
  Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs. 328-339
  
• Jirí Fiala, Daniël Paulusma, Jan Arne Telle:
  Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms. 340-351
  
• Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, Roberto Solis-Oba:
  Packing Weighted Rectangles into a Square. 352-363
  
• Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse:
  Nondeterministic Graph Searching: From Pathwidth to Treewidth. 364-375
  
• Joxe Gaintzarain, Montserrat Hermo, Marisa Navarro:
  Goals in the Propositional Horn Language Are Monotone Boolean Circuits. 376-386
  
• Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang:
  Autoreducibility, Mitoticity, and Immunity. 387-398
  
• Christian Glaßer, Alan L. Selman, Liyu Zhang:
  Canonical Disjoint NP-Pairs of Propositional Proof Systems. 399-409
  
• Judy Goldsmith, Matthias Hagen, Martin Mundhenk:
  Complexity of DNF and Isomorphism of Monotone Formulas. 410-421
  
• Martin Grohe, Stephan Kreutzer, Nicole Schweikardt:
  The Expressive Power of Two-Variable Least Fixed-Point Logics. 422-434
  
• Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov:
  Languages Representable by Vertex-Labeled Graphs. 435-446
  
• Leonid Gurvits:
  On the Complexity of Mixed Discriminants and Related Problems. 447-458
  
• Uffe Flarup Hansen, Klaus Meer:
  Two Logical Hierarchies of Optimization Problems over the Real Numbers. 459-470
  
• Bernhard Heinemann:
  Algebras as Knowledge Structures. 471-482
  
• André Hernich, Arfst Nickelsen:
  Combining Self-reducibility and Partial Information Algorithms. 483-494
  
• Paul Hunter, Anuj Dawar:
  Complexity Bounds for Regular Games. 495-506
  
• Ryszard Janicki:
  Basic Mereology with Equivalence Relations. 507-519
  
• Jesper Jansson, Zeshan Peng:
  Online and Dynamic Recognition of Squarefree Strings. 520-531
  
• Tomasz Jurdzinski, Friedrich Otto:
  Shrinking Restarting Automata. 532-543
  
• Christos A. Kapoutsis:
  Removing Bidirectionality from Nondeterministic Finite Automata. 544-555
  
• Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich:
  Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities. 556-567
  
• Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith:
  On the Parameterized Complexity of Exact Satisfiability Problems. 568-579
  
• Petr Kolman:
  Approximating Reversal Distance for Strings with Bounded Number of Duplicates. 580-590
  
• Konstantin Korovin, Andrei Voronkov:
  Random Databases and Threshold for Monotone Non-recursive Datalog. 591-602
  
• Daniel Král, Ondrej Pangrác:
  An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems. 603-614
  
• Piotr Krysta:
  Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. 615-627
  
• Fredrik Kuivinen:
  Tight Approximability Results for the Maximum Solution Equation Problem over Z_p. 628-639
  
• Martin Lange, Rafal Somla:
  The Complexity of Model Checking Higher Order Fixpoint Logic. 640-651
  
• Minming Li, Frances F. Yao:
  An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. 652-663
  
• Markus Lohrey, Nicole Ondrusch:
  Inverse Monoids: Decidability and Complexity of Algebraic Questions. 664-675
  
• María López-Valdés, Elvira Mayordomo:
  Dimension Is Compression. 676-685
  
• Rémi Morin:
  Concurrent Automata vs. Asynchronous Systems. 686-698
  
• Hidenosuke Nishio:
  Completeness and Degeneracy in Information Dynamics of Cellular Automata. 699-707
  
• Alexander Okhotin:
  Strict Language Inequalities and Their Decision Problems. 708-719
  
• G. Michele Pinna:
  Event Structures for the Collective Tokens Philosophy of Inhibitor Nets. 720-732
  
• Tobias Riege, Jörg Rothe:
  An Exact 2.9416ⁿ Algorithm for the Three Domatic Number Problem. 733-744
  
• Mohammad Ali Safari:
  D-Width: A More Natural Measure for Directed Tree Width. 745-756
  
• Jakob Grue Simonsen:
  On Beta-Shifts Having Arithmetical Languages. 757-768
  
• Jaco van de Pol, Olga Tveretina:
  A BDD-Representation for the Logic of Equality and Uninterpreted Functions. 769-780
  
• Falk Unger:
  On Small Hard Leaf Languages. 781-792
  
• Virginia Vassilevska:
  Explicit Inapproximability Bounds for the Shortest Superstring Problem. 793-800
  
• Michal Wrona:
  Stratified Boolean Grammars. 801-812