Not logged in
Path: Menu > Accepted Papers

MFCS 2012 Accepted Papers

Gabriele Fici: A Characterization of Bispecial Sturmian Words
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Onufry Wojtaszczyk: Sitting closer to friends than enemies, revisited
Francine Blanchet-Sadri and Sean Simmons: Abelian Pattern Avoidance in Partial Words
Christos Kapoutsis and Giovanni Pighizzini: Reversal Hierarchies for Small 2DFAs
Petr Golovach, Daniel Paulusma and Bernard Ries: Coloring Graphs Characterized by a Forbidden Subgraph
Martin Delacourt and Petr Kurka: Finite State Transducers for Modular Möbius Number Systems
Therese Biedl and Peter Floderus: Drawing planar graphs on points inside a polygon
Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis: Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs
Olivier Bournez, Pierre Fraigniaud and Xavier Koegler: Computing with Large Populations Using Interactions
Petr Golovach, Pim Van 'T Hof and Daniel Paulusma: Obtaining Planarity by Contracting Few Edges
Eric Allender, Harry Buhrman, Luke Friedman and Bruno Loff: Reductions to the Set of Random Strings: the Resource-Bounded Case
Tatsuya Akutsu and Takeyuki Tamura: A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree
Ville Salo and Ilkka Törmä: Computational Aspects of Cellular Automata on Countable Sofic Shifts
Nicolas de Rugy-Altherre: A Dichotomy Theorem for Homomorphism polynomials
Laurent Bulteau, Guillaume Fertin and Irena Rusu: Pancake Flipping Is Hard
Thomas Weidner: Probabilistic Automata and Probabilistic Logic
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar and Yadu Vasudev: Near-Optimal Expanding Generating Sets for Solvable Permutation Groups
Andreas Emil Feldmann: Fast Balanced Partitioning is Hard, Even on Grids and Trees
Taolue Chen, Klaus Dräger and Stefan Kiefer: Model Checking Stochastic Branching Processes
Katja Losemann, Wim Martens and Matthias Niewerth: Descriptive Complexity of Deterministic Regular Expressions
V: Arvind, Johannes Köbler, Sebastian Kuhnert and Yadu Vasudev: Approximate Graph Isomorphism
Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita and Sebastien Tixeuil: Gathering an even number of robots in a symmetric ring without global multiplicity detection
Alexander Kartzow and Pawel Parys: Strictness of the Collapsible Pushdown Hierarchy
Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Anders Yeo: Parameterized Study of the Test Cover Problem
Tatiana Starikovskaya: Computing Lempel-Ziv Factorization Online
Manfred Kufleitner and Alexander Lauser: The Join Levels of the Trotter-Weil Hierarchy are Decidable
Dietmar Berwanger, Lukasz Kaiser and Simon Leßenich: Solving Counter Parity Games
Martin Doucha and Jan Kratochvil: Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
Filip Murlak, Michał Ogiński and Marcin Przybyłko: Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
Michelangelo Grigni and Hao-Hsiang Hung: Light Spanners in Bounded Pathwidth Graphs
Klaus Jansen and Stefan Kraft: An Improved Approximation Scheme for Variable-Sized Bin Packing
Tom Friedetzky, Leszek Gasieniec, Thomas Gorry and Russell Martin: Observe and remain silent (Communication-less agent location discovery)
Cristina Bazgan and Morgan Chopin: The Robust Set problem: parameterized complexity and approximation
Jingsen Chen, Stefan Edelkamp, Amr Elmasry and Jyrki Katajainen: In-Place Heap Construction with Optimized Comparisons, Moves, and Cache Misses
Tommi Lehtinen: Equations X+A=B and (X+X)+C=(X-X)+D over sets of natural numbers
Markus Blaeser and Bodo Manthey: Smoothed Complexity Theory
Giovanni Di Crescenzo and Vadym Fedyukovych: Zero-Knowledge Proofs via Polynomial Representations
Elena Petrova and Arseny Shur: Constructing Premaximal Ternary Square-Free Words of Any Level
Igor Tunev and Arseny Shur: On Two Stronger Versions of Dejean's Conjecture
Marcus Gelderie: Strategy Machines and their Complexity
Radu Mardare, Prakash Panangaden and Kim Guldstrand Larsen: Take it to the limit: Approximate reasoning for Markov processes
Robert Ganian, Petr Hlineny, Jaroslav Nesetril, Jan Obdrzalek, Patrice Ossona de Mendez and Reshma Ramadurai: When Trees Grow Low: Shrubs and Fast MSO1
Florin Manea, Robert Mercas and Dirk Nowotka: Fine and Wilf theorem and pseudo-repetitions
Mingyu Xiao and Jiong Guo: A Quadric Vertex Kernel for Feedback Arc Set in Bipartite Tournaments
Stefan Repke and Christof Löding: Regularity Problems for Weak Pushdown ?-Automata and Games
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub and Thomas Thierauf: Planarizing Gadgets for Perfect Matching do not Exist
Torben Hagerup: Kernels for Edge Dominating Set: Simpler or Smaller
David Janin: Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles
Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick and Martin Ziegler: Computational Complexity of Smooth Differential Equations
Angelo Fanelli, Luca Moscardelli and Alexander Skopalik: On the Impact of Fair Best Response Dynamics
Bonsma: The complexity of rerouting shortest paths
Dorit Pardo and Alexander Rabinovich: A Finite Basis for "Almost Future" Temporal Logic over the Reals
Lauri Ahlroth and Pekka Orponen: Unordered Constraint Satisfaction Games
Andreas Krebs, Christoph Behle, Pierre Mckenzie and Klaus-Joern Lange: The lower reaches of circuit uniformity
Davide Bil? and Anna Zych: New Advances in reoptimizing the Minimum Steiner Tree problem
Anthony Widjaja Lin: Weakly-Synchronized Ground Tree Rewriting (with applications to verifying multithreaded programs)
Eugene Asarin, Nicolas Basset, Aldric Degorre and Dominique Perrin: Generating functions of timed languages
Meena Mahajan, Raghavendra Rao B V and Karteek Sreenivasaiah: Identity Testing, multilinearity testing, and monomials  in Read-Once/Twice Formulas and Branching Programs
Jesper Nederlof, Erik Jan van Leeuwen and Ruben van der Zwaan: Reducing a Target Interval to a Few Exact Queries
Dimitris Fotakis and Paraschos Koutris: Online Sum-Radii Clustering
Matus Mihalak and Jan Christoph Schlegel: Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games
Paul Bell, Mika Hirvensalo and Igor Potapov: Mortality for 2x2 matrices is NP-hard
Furio Honsell, Marina Lenisa and Rekha Redamalla: Categories of Coalgebraic Games