LIST OF ACCEPTED PAPERS

  • Vladimir E. Alekseev, Vadim Lozin, Dmitriy Malyshev and Martin Milanic; The Maximum Independent Set Problem in Planar Graphs
  • Vittorio Bilò, Angelo Fanelli, Michele Flammini and Luca Moscardelli; When Ignorance Helps: Graphical Multicast Cost Sharing Games
  • Marek Biskup; Shortest Synchronizing Strings for Huffman Codes
  • Henrik Björklund, Wim Martens and Thomas Schwentick; Optimizing Conjunctive Queries over Trees using Schema Information
  • Hans L. Bodlaender, Michael Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos and Frances A. Rosamond; Clustering with partial information
  • Hans-Joachim Boeckenhauer and Dennis Komm; Reoptimization of the Metric Deadline TSP
  • Joan Boyar, Rene Peralta and Philip Matthews; On the shortest linear straight-line program for computing linear forms
  • Mathieu Brevilliers, Nicolas Chevallier and Dominique Schmitt; Flip Algorithm for Segment Triangulations
  • Hajo Broersma and Daniel Paulusma; Computing sharp 2-factors in claw-free graphs
  • Ioannis Caragiannis and Gianpiero Monaco; A $6/5$-approximation algorithm for the maximum $3$-cover problem
  • Arnaud Carayol and Michaela Slaats; Positional Strategies for Higher-Order Pushdown Parity Games
  • Venkatesan Chakaravarthy and Sambuddha Roy; Arthur and Merlin as Oracles
  • Emilie Charlier and Michel Rigo; A decision problem for ultimately periodic sets in non-standard numeration systems
  • Alessandra Cherubini, Stefano Crespi-Reghizzi and Matteo Pradella; Regional languages and tiling: a unifying approach to picture grammars
  • Claire David; Complexity of Data Tree Patterns over XML documents
  • Elena Czeizler, Lila Kari and Shinnosuke Seki; On a special class of primitive words
  • Feodor Dragan, Fedor Fomin and Petr Golovach; A PTAS for the sparsest spanners problem on apex-minor-free graphs
  • Michael Elberfeld and Till Tantau; Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
  • Gabor Erdelyi, Markus Nowak and Jörg Rothe; Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
  • Alain Finkel and Arnaud Sangnier; Reversal-bounded counter machines revisited
  • Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff and Saket Saurabh; Iterative Compression and Exact Algorithms
  • Hervé Fournier, Danièle Gardy, Antoine Genitrini and Bernhard Gittenberger; Complexity and Asymptotic Density of Boolean Functions over Implication
  • Wouter Gelade; Succinctness of regular expressions with interleaving, intersection and counting
  • Pierre Guillon and Gaétan Richard; Nilpotency and limit sets of cellular automata
  • Chinh T. Hoang, Marcin Kaminski, Vadim Lozin, Joe Sawada and Xiao Shu; A note on k-colourability of P_5-free graphs
  • Christian Hundt and Maciej Liskiewicz; Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations
  • Maurice Jansen; Lower bounds for Syntactically Multilinear Algebraic Branching Programs
  • Jarkko Kari and Nicolas Ollinger; Periodicity and Immortality in Reversible Computing
  • Lukasz Krzywiecki, Anna Lauks, Marek Klonowski and Kutylowski Miroslaw; Step-out Ring Signatures
  • Manfred Kufleitner; The Height of Factorization Forests
  • Meena Mahajan and Raghavendra Rao B V; Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae
  • Bodo Manthey and Till Tantau; Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise
  • Radu Mardare and Alberto Policriti; A complete axiomatic system for a process-based Spatial Logic
  • Marios Mavronicolas, Vicky Papadopoulou, Burkhard Monien and Florian Schoppmann; Voronoi Games on Cycle Graphs
  • Andrew McGrae and Michele Zito; Colouring random empire trees
  • Kai Plociennik; Approximating Independent Set and Coloring in Random Uniform Hypergraphs
  • Daniel Raible and Henning Fernau; A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
  • Damien Regnault; Directed Percolation arising in Stochastic Cellular Automata Analysis
  • Mark Rhodes; Resolution Width and Cutting Plane Rank are Incomparable
  • Andrei Romashchenko and Andrei Muchnik; A random oracle does not help extract the mutual information
  • Jacques Sakarovitch and Rodrigo de Souza; On the decidability of bounded valuedness for transducers
  • Antonino Salibra and Giulio Manzonetto; From Lambda Calculus to Universal Algebra and Back
  • Numan Sheikh and Sarmad Abbasi; Question/Answer Games on Towers and Pyramids
  • Stefan Szeider; Monadic Second Order Logic on Graphs with Local Cardinality Constraints
  • Aleksander Wojdyga; Short proofs of strong normalization
WMiI UMK