32. MFCS 2007: Ceský Krumlov, Czech Republic

Ludek Kucera, Antonín Kucera (Eds.): Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings. Lecture Notes in Computer Science 4708 Springer 2007, ISBN 978-3-540-74455-9

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 23 17:41:07 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page