32. MFCS 2007: Ceský Krumlov, Czech Republic

Invited Papers

• Vasek Chvátal:
  How To Be Fickle. 1
  
• Anuj Dawar:
  Finite Model Theory on Tame Classes of Structures. 2-12
  
• Kurt Mehlhorn:
  Minimum Cycle Bases in Graphs Algorithms and Applications. 13-14
  
• C.-H. Luke Ong:
  Hierarchies of Infinite Structures Generated by Pushdown Automata and Recursion Schemes. 15-21
  
• Leslie G. Valiant:
  Evolvability. 22-43
  

Random Graphs

• Sotiris E. Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis:
  Expander Properties and the Cover Time of Random Intersection Graphs. 44-55
  
• William Duckworth, Michele Zito:
  Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs. 56-66
  

Rewriting

• Christof Löding, Alex Spelten:
  Transition Graphs of Rewriting Systems over Unranked Trees. 67-77
  
• Foto N. Afrati:
  Rewriting Conjunctive Queries Determined by Views. 78-89
  

Approximation Algorithms

• Gábor Salamon:
  Approximation Algorithms for the Maximum Internal Spanning Tree Problem. 90-102
  
• Klaus Jansen, Roberto Solis-Oba:
  New Approximability Results for 2-Dimensional Packing Problems. 103-114
  
• Yuichi Asahiro, Eiji Miyano, Toshihide Murata, Hirotaka Ono:
  On Approximation of Bookmark Assignments. 115-124
  

Automata and Circuits

• Dirk Nowotka, Jirí Srba:
  Height-Deterministic Pushdown Automata. 125-134
  
• Patrick Chervet, Igor Walukiewicz:
  Minimizing Variants of Visibly Pushdown Automata. 135-146
  
• Christoph Behle, Andreas Krebs, Mark Mercer:
  Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids. 147-158
  

Complexity I

• Jaroslav Nesetril, Mark H. Siggers:
  Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete. 159-170
  
• Gábor Kun, Jaroslav Nesetril:
  NP by Means of Lifts and Shadows. 171-181
  
• Luc Longpré, Pierre McKenzie:
  The Complexity of Solitaire. 182-193
  

Streams and Compression

• Camil Demetrescu, Bruno Escoffier, Gabriel Moruz, Andrea Ribichini:
  Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems. 194-205
  
• Travis Gagie, Giovanni Manzini:
  Space-Conscious Compression. 206-217
  

Graphs I

• Rodolfo Carvajal, Martín Matamala, Ivan Rapaport, Nicolas Schabanel:
  Small Alliances in Graphs. 218-227
  
• Peter Jonsson, Gustav Nordh, Johan Thapper:
  The Maximum Solution Problem on Graphs. 228-239
  

Iteration and Recursion

• Jirí Adámek, Stefan Milius, Jiri Velebil:
  What Are Iteration Theories? 240-252
  
• John Case, Samuel E. Moelius:
  Properties Complementary to Program Self-reference. 253-263
  

Algorithms I

• Kasper Pedersen:
  Dobrushin Conditions for Systematic Scan with Block Dynamics. 264-275
  
• Daniel Lokshtanov:
  On the Complexity of Computing Treelength. 276-287
  
• Csanád Imreh, Tamás Németh:
  On Time Lookahead Algorithms for the Online Data Acknowledgement Problem. 288-297
  

Automata

• Martin Delacourt, Victor Poupet:
  Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-convex Neighborhoods. 298-309
  
• Julien Cervelle, Pierre Guillon:
  Towards a Rice Theorem on Traces of Cellular Automata. 310-319
  
• Damien Regnault, Nicolas Schabanel, Eric Thierry:
  Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority. 320-332
  

Complexity II

• Rupert J. Hartung, Claus-Peter Schnorr:
  Public Key Identification Based on the Equivalence of Quadratic Forms. 333-345
  
• Paul Bell, Igor Potapov:
  Reachability Problems in Quaternion Matrix and Rotation Semigroups. 346-358
  
• Pascal Koiran, Sylvain Perifel:
  VPSPACE and a Transfer Theorem over the Complex Field. 359-370
  

Protocols

• Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci:
  Efficient Provably-Secure Hierarchical Key Assignment Schemes. 371-382
  
• Amit Chakrabarti, Anna Shubina:
  Nearly Private Information Retrieval. 383-393
  

Graphs II

• Fabrizio Frati, Markus Geyer, Michael Kaufmann:
  Packing and Squeezing Subgraphs into Planar Graphs. 394-405
  
• Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel:
  Dynamic Matchings in Convex Bipartite Graphs. 406-417
  

Networks

• Evangelos Kranakis, Michel Paquette, Andrzej Pelc:
  Communication in Networks with Random Dependent Faults. 418-429
  
• Andrea E. F. Clementi, Angelo Monti, Francesco Pasquale, Riccardo Silvestri:
  Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults. 430-441
  

Algorithms II

• Gerth Stølting Brodal, Allan Grønlund Jørgensen:
  A Linear Time Algorithm for the k Maximal Sums Problem. 442-453
  
• Elias Koutsoupias, Angelina Vidali:
  A Lower Bound of 1+phi for Truthful Scheduling Mechanisms. 454-464
  
• Maxime Crochemore, Lucian Ilie:
  Analysis of Maximal Repetitions in Strings. 465-476
  

Languages

• Nicolas Bedon, Chloe Rispal:
  Series-Parallel Languages on Scattered and Countable Posets. 477-488
  
• Antoine Meyer:
  Traces of Term-Automatic Graphs. 489-500
  
• Yo-Sub Han, Kai Salomaa:
  State Complexity of Basic Operations on Suffix-Free Regular Languages. 501-512
  

Graphs III

• Jan Kratochvíl, Dieter Kratsch, Mathieu Liedloff:
  Exact Algorithms for L (2, 1)-Labeling of Graphs. 513-524
  
• Andreas Brandstädt, Peter Wagner:
  On ( k , l)-Leaf Powers. 525-535
  

Quantum Computing

• Seiichiro Tani:
  An Improved Claw Finding Algorithm Using Quantum Walk. 536-547
  
• Rahul Tripathi:
  Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument. 548-558
  

Isomorphism

• Joaquim Gabarró, Alina García, Maria J. Serna:
  On the Complexity of Game Isomorphism. 559-571
  
• Fabian Wagner:
  Hardness Results for Tournament Isomorphism and Automorphism. 572-583
  
• Takayuki Nagoya, Seinosuke Toda:
  Relating Complete and Partial Solution for Problems Similar to Graph Automorphism. 584-595
  

Equilibria

• Spyros C. Kontogiannis, Paul G. Spirakis:
  Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach. 596-608
  
• Elias Koutsoupias, Panagiota N. Panagopoulou, Paul G. Spirakis:
  Selfish Load Balancing Under Partial Knowledge. 609-620
  
• Vittorio Bilò, Michele Flammini:
  Extending the Notion of Rationality of Selfish Agents: Second Order Nash Equilibria. 621-632
  

Games

• Marios Mavronicolas, Igal Milchtaich, Burkhard Monien, Karsten Tiemann:
  Congestion Games with Player-Specific Constants. 633-644
  
• Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman:
  Finding Patterns in Given Intervals. 645-656
  
• Yvonne Bleischwitz, Burkhard Monien, Florian Schoppmann, Karsten Tiemann:
  The Power of Two Prices: Beyond Cross-Monotonicity. 657-668
  

Algebra and Strings

• Markus Bläser, Andreas Meyer de Voltaire:
  Semisimple Algebras of Almost Minimal Rank over the Reals. 669-680
  
• Esko Ukkonen:
  Structural Analysis of Gapped Motifs of a String. 681-690
  

Algorithms III

• Torben Hagerup:
  Online and Offline Access to Short Lists. 691-702
  
• Riko Jacob:
  Optimal Randomized Comparison Based Algorithms for Collision. 703-714
  
• Christos Nomikos, Aris Pagourtzis, Stathis Zachos:
  Randomized and Approximation Algorithms for Blue-Red Matching. 715-725
  

Words and Graphs

• Klaus Meer, Martin Ziegler:
  Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation. 726-737
  
• Paul S. Bonsma, Luis Cereceda:
  Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances. 738-749
  
• Henrik Björklund, Mikolaj Bojanczyk:
  Shuffle Expressions and Words with Nested Data. 750-761
  

Last update Thu May 24 04:37:39 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page