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 BibTeX

Invited Papers

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

Random Graphs

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

Rewriting

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

Approximation Algorithms

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

Automata and Circuits

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

Complexity I

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

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
Electronic Edition (link) BibTeX
Travis Gagie, Giovanni Manzini:
Space-Conscious Compression. 206-217
Electronic Edition (link) BibTeX

Graphs I

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

Iteration and Recursion

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

Algorithms I

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

Automata

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

Complexity II

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

Protocols

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

Graphs II

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

Networks

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

Algorithms II

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

Languages

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

Graphs III

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

Quantum Computing

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

Isomorphism

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

Equilibria

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

Games

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

Algebra and Strings

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

Algorithms III

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

Words and Graphs

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