35. MFCS 2010: Brno, Czech Republic

• Andris Ambainis:
  New Developments in Quantum Algorithms. 1-11
  
• Paul Bendich, Herbert Edelsbrunner, Michael Kerber, Amit K. Patel:
  Persistent Homology under Non-uniform Error. 12-23
  
• Juraj Hromkovic, Rastislav Královic, Richard Královic:
  Information Complexity of Online Problems. 24-36
  
• Daniel Lokshtanov:
  Algorithmic Lower Bounds for Problems on Decomposable Graphs. 37
  
• Bojan Mohar:
  Do We Really Understand the Crossing Numbers? 38-41
  
• Dmitri Akatov, Georg Gottlob:
  Balanced Queries: Divide and Conquer. 42-54
  
• Dimitry S. Ananichev, Vladimir V. Gusev, Mikhail V. Volkov:
  Slowly Synchronizing Automata and Digraphs. 55-65
  
• László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, Xiaoming Sun:
  Weights of Exact Threshold Functions. 66-77
  
• Yoram Bachrach, Michael Zuckerman, Michael Wooldridge, Jeffrey S. Rosenschein:
  Proof Systems and Transformation Games. 78-89
  
• Sanjoy K. Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie:
  Scheduling Real-Time Mixed-Criticality Jobs. 90-101
  
• Anguraj Baskar, Ramaswamy Ramanujam, S. P. Suresh:
  A dexptime-Complete Dolev-Yao Theory with Distributive Encryption. 102-113
  
• Nadja Betzler:
  On Problem Kernels for Possible Winner Determination under the k-Approval Protocol. 114-125
  
• Ivona Bezáková, Adam J. Friedlander:
  Counting Minimum (s, t)-Cuts in Weighted Planar Graphs in Polynomial Time. 126-137
  
• Davide Bilò, Luciano Gualà, Guido Proietti:
  Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree. 138-149
  
• Davide Bilò, Luciano Gualà, Guido Proietti:
  Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems. 150-161
  
• Manuel Bodirsky, Víctor Dalmau, Barnaby Martin, Michael Pinsker:
  Distance Constraint Satisfaction Problems. 162-173
  
• Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, Martin Vatshelle:
  Faster Algorithms on Branch and Clique Decompositions. 174-185
  
• Beate Bollig:
  Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks. 186-197
  
• Olivier Bournez, Daniel S. Graça, Emmanuel Hainry:
  Robust Computations with Dynamical Systems. 198-208
  
• Laurent Boyer, Guillaume Theyssier:
  On Factor Universality in Symbolic Spaces. 209-220
  
• Nader H. Bshouty, Hanna Mazzawi:
  Toward a Deterministic Polynomial Time Algorithm with Optimal Additive Query Complexity. 221-232
  
• Alberto Carraro, Thomas Ehrhard, Antonino Salibra:
  Resource Combinatory Algebras. 233-245
  
• Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, Thomas A. Henzinger:
  Randomness for Free. 246-257
  
• Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger:
  Qualitative Analysis of Partially-Observable Markov Decision Processes. 258-269
  
• Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, Paul G. Spirakis:
  All Symmetric Predicates in NSPACE(n²) Are Stably Computable by the Mediated Population Protocol Model. 270-281
  
• János Csirik, Leah Epstein, Csanád Imreh, Asaf Levin:
  Online Clustering with Variable Sized Clusters. 282-293
  
• Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc:
  Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains. 294-305
  
• Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, Heribert Vollmer:
  Counting Classes and the Fine Structure between NC¹ and L. 306-317
  
• Julien David:
  The Average Complexity of Moore's State Minimization Algorithm Is O(n log log n). 318-329
  
• Dariusz Dereniowski:
  Connected Searching of Weighted Trees. 330-341
  
• Emmanuel Filiot, Tristan Le Gall, Jean-François Raskin:
  Iterated Regret Minimization in Game Graphs. 342-354
  
• Emmanuel Filiot, Jean-François Raskin, Pierre-Alain Reynier, Frédéric Servais, Jean-Marc Talbot:
  Properties of Visibly Pushdown Transducers. 355-367
  
• Marcelo P. Fiore, Ola Mahmoud:
  Second-Order Algebraic Theories - (Extended Abstract). 368-380
  
• Gaëlle Fontaine, Thomas Place:
  Frame Definability for Classes of Trees in the µ-calculus. 381-392
  
• Gero Greiner, Riko Jacob:
  Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model. 393-404
  
• Sylvain Guillemot, Florian Sikora:
  Finding and Counting Vertex-Colored Subtrees. 405-416
  
• Jing He, Hongyu Liang, Jayalal M. N. Sarma:
  Limiting Negations in Bounded Treewidth and Upward Planar Circuits. 417-428
  
• Szczepan Hummel, Michal Skrzypczak, Szymon Torunczyk:
  On the Topological Complexity of MSO+U and Related Automata Models. 429-440
  
• Artur Jez, Alexander Okhotin:
  Least and Greatest Solutions of Equations over Sets of Integers. 441-452
  
• Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh:
  Improved Simulation of Nondeterministic Turing Machines. 453-464
  
• Naoyuki Kamiyama:
  The Prize-Collecting Edge Dominating Set Problem in Trees. 465-476
  
• Bruno Grenet, Pascal Koiran, Natacha Portier:
  The Multivariate Resultant Is NP-hard in Any Characteristic. 477-488
  
• Stefan Kratsch, Dániel Marx, Magnus Wahlström:
  Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems. 489-500
  
• Yoshifumi Manabe, Tatsuaki Okamoto:
  Meta-Envy-Free Cake-Cutting Protocols. 501-512
  
• Amaldev Manuel:
  Two Variables and Two Successors. 513-524
  
• Giulio Manzonetto, Paolo Tranquilli:
  Harnessing ML^F with the Power of System F. 525-536
  
• Manfred Droste, Ingmar Meinecke:
  Describing Average- and Longtime-Behavior by Weighted MSO Logics. 537-548
  
• Neeldhara Misra, N. S. Narayanaswamy, Venkatesh Raman, Bal Sri Shankar:
  Solving minones-2-sat as Fast as vertex cover. 549-555
  
• Alexander Okhotin:
  Unambiguous Finite Automata over a Unary Alphabet. 556-567
  
• Jörg Olschewski, Michael Ummels:
  The Complexity of Finding Reset Words in Finite Automata. 568-579
  
• M. Praveen:
  Does Treewidth Help in Modal Satisfiability? - (Extended Abstract). 580-591
  
• Bernd Puchala:
  Asynchronous Omega-Regular Games with Partial Information. 592-603
  
• Bernd Puchala, Roman Rabinovich:
  Parity Games with Partial Information Played on Graphs of Bounded Complexity. 604-615
  
• Philippe Schnoebelen:
  Revisiting Ackermann-Hardness for Lossy Counter Machines and Reset Petri Nets. 616-628
  
• Yann Strozecki:
  Enumeration of the Monomials of a Polynomial and Related Complexity Classes. 629-640
  
• Siamak Tazari:
  Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs. 641-652
  
• Bahareh Badban, Mohammad Torabi Dashti:
  Semi-linear Parikh Images of Regular Expressions via Reduction. 653-664
  
• Kenya Ueno:
  Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds. 665-676
  
• Ho-Lun Cheng, Ke Yan:
  Mesh Deformation of Dynamic Smooth Manifolds with Surface Correspondences. 677-688
  
• Marius Zimand:
  Counting Dependent and Independent Strings. 689-700
  
• Marius Zimand:
  Impossibility of Independence Amplification in Kolmogorov Complexity Theory. 701-712
  

Last update Fri May 25 08:26:28 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page