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 updated on Thu May 23 03:37:38 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page