26. STACS 2009:
Freiburg,
Germany
Susanne Albers, Jean-Yves Marion (Eds.):
26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings.
Dagstuhl Seminar Proceedings 09001 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany/Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2009, ISBN 978-3-939897-09-5 BibTeX
Invited Papers
Contributed Papers
- Mustaq Ahmed, Anna Lubiw:
Shortest Paths Avoiding Forbidden Subpaths.
63-74
Electronic Edition (link) BibTeX
- Joël Alwen, Chris Peikert:
Generating Shorter Bases for Hard Random Lattices.
75-86
Electronic Edition (link) BibTeX
- Vikraman Arvind, Partha Mukhopadhyay:
Quantum Query Complexity of Multilinear Identity Testing.
87-98
Electronic Edition (link) BibTeX
- Nathalie Aubrun, Mathieu Sablik:
An Order on Sets of Tilings Corresponding to an Order on Languages.
99-110
Electronic Edition (link) BibTeX
- Jérémy Barbay, Gonzalo Navarro:
Compressed Representations of Permutations, and Applications.
111-122
Electronic Edition (link) BibTeX
- Frédérique Bassino, Julien David, Cyril Nicaud:
On the Average Complexity of Moore's State Minimization Algorithm.
123-134
Electronic Edition (link) BibTeX
- Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-Linear Properties.
135-146
Electronic Edition (link) BibTeX
- Laurent Bienvenu, Rod Downey:
Kolmogorov Complexity and Solovay Functions.
147-158
Electronic Edition (link) BibTeX
- Mikolaj Bojanczyk:
Weak MSO with the Unbounding Quantifier.
159-170
Electronic Edition (link) BibTeX
- Glencora Borradaile, Erik D. Demaine, Siamak Tazari:
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs.
171-182
Electronic Edition (link) BibTeX
- Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo:
A Polynomial Kernel for Multicut in Trees.
183-194
Electronic Edition (link) BibTeX
- Laurent Boyer, Guillaume Theyssier:
On Local Symmetries and Universality in Cellular Automata.
195-206
Electronic Edition (link) BibTeX
- Tomás Brázdil, Václav Brozek, Antonín Kucera, Jan Obdrzálek:
Qualitative Reachability in Stochastic BPA Games.
207-218
Electronic Edition (link) BibTeX
- Jop Briet, Ronald de Wolf:
Locally Decodable Quantum Codes.
219-230
Electronic Edition (link) BibTeX
- Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx:
Enumerating Homomorphisms.
231-242
Electronic Edition (link) BibTeX
- Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster:
Hardness and Algorithms for Rainbow Connectivity.
243-254
Electronic Edition (link) BibTeX
- Ho-Leung Chan, Jeff Edmonds, Tak Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs:
Nonclairvoyant Speed Scaling for Flow and Energy.
255-264
Electronic Edition (link) BibTeX
- Victor Chepoi, Morgan Seston:
An Approximation Algorithm for linfinity Fitting Robinson Structures to Distances.
265-276
Electronic Edition (link) BibTeX
- Mahdi Cheraghchi, Amin Shokrollahi:
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties.
277-288
Electronic Edition (link) BibTeX
- Julien Clément, Maxime Crochemore, Giuseppina Rindone:
Reverse Engineering Prefix Tables.
289-300
Electronic Edition (link) BibTeX
- Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam:
The Price of Anarchy in Cooperative Network Creation Games.
301-312
Electronic Edition (link) BibTeX
- Ronald de Wolf:
Error-Correcting Data Structures.
313-324
Electronic Edition (link) BibTeX
- Volker Diekert, Manfred Kufleitner:
Fragments of First-Order Logic over Infinite Words.
325-336
Electronic Edition (link) BibTeX
- Pietro di Lena, Luciano Margara:
Undecidable Properties of Limit Set Dynamics of Cellular Automata.
337-347
Electronic Edition (link) BibTeX
- Tomás Ebenlendr, Jiri Sgall:
Semi-Online Preemptive Scheduling: One Algorithm for All Variants.
349-360
Electronic Edition (link) BibTeX
- Khaled M. Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, Domagoj Severdija:
Improved Approximations for Guarding 1.5-Dimensional Terrains.
361-371
Electronic Edition (link) BibTeX
- Robert Elsässer, Thomas Sauerwald:
Cover Time and Broadcast Time.
373-384
Electronic Edition (link) BibTeX
- Matthias Englert, Heiko Röglin, Jacob Spönemann, Berthold Vöcking:
Economical Caching.
385-396
Electronic Edition (link) BibTeX
- Babak Farzad, Lap Chi Lau, Van Bang Le, Nguyen Ngoc Tuy:
Computing Graph Roots Without Short Cycles.
397-408
Electronic Edition (link) BibTeX
- Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier:
A Generalization of Nemhauser and Trotter's Local Optimization Theorem.
409-420
Electronic Edition (link) BibTeX
- Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, Yngve Villanger:
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves.
421-432
Electronic Edition (link) BibTeX
- Alain Finkel, Jean Goubault-Larrecq:
Forward Analysis for WSTS, Part I: Completions.
433-444
Electronic Edition (link) BibTeX
- Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos:
Approximating Acyclicity Parameters of Sparse Hypergraphs.
445-456
Electronic Edition (link) BibTeX
- Gianni Franceschini, Roberto Grossi, S. Muthukrishnan:
Optimal Cache-Aware Suffix Selection.
457-468
Electronic Edition (link) BibTeX
- Péter Gács, Mathieu Hoyrup, Cristobal Rojas:
Randomness on Computable Probability Spaces - A Dynamical Point of View.
469-480
Electronic Edition (link) BibTeX
- Wouter Gelade, Marcel Marquardt, Thomas Schwentick:
The Dynamic Complexity of Formal Languages.
481-492
Electronic Edition (link) BibTeX
- Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley:
A Complexity Dichotomy for Partition Functions with Mixed Signs.
493-504
Electronic Edition (link) BibTeX
- Andre Gronemeier:
Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness.
505-516
Electronic Edition (link) BibTeX
- Roberto Grossi, Alessio Orlandi, Rajeev Raman, S. Srinivasa Rao:
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries.
517-528
Electronic Edition (link) BibTeX
- Danny Hermelin, Gad M. Landau, Shir Landau, Oren Weimann:
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression.
529-540
Electronic Edition (link) BibTeX
- Florian Horn:
Random Fruits on the Zielonka Tree.
541-552
Electronic Edition (link) BibTeX
- Juraj Hromkovic, Georg Schnitger:
Ambiguity and Communication.
553-564
Electronic Edition (link) BibTeX
- Szczepan Hummel, Henryk Michalewski, Damian Niwinski:
On the Borel Inseparability of Game Tree Languages.
565-575
Electronic Edition (link) BibTeX
- Artur Jez, Alexander Okhotin:
Equations over Sets of Natural Numbers with Addition Only.
577-588
Electronic Edition (link) BibTeX
- Daniel Kirsten, Sylvain Lombardy:
Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata.
589-600
Electronic Edition (link) BibTeX
- Stefan Kratsch:
Polynomial Kernelizations for MIN F+Pi1 and MAX NP.
601-612
Electronic Edition (link) BibTeX
- Fabian Kuhn:
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time.
613-624
Electronic Edition (link) BibTeX
- Francois Le Gall:
Efficient Isomorphism Testing for a Class of Group Extensions.
625-636
Electronic Edition (link) BibTeX
- Bodo Manthey:
On Approximating Multi-Criteria TSP.
637-648
Electronic Edition (link) BibTeX
- Dániel Marx:
Tractable Structures for Constraint Satisfaction with Truth Tables.
649-660
Electronic Edition (link) BibTeX
- Sven Schewe:
Büchi Complementation Made Tight.
661-672
Electronic Edition (link) BibTeX
- Lutz Schröder, Dirk Pattinson:
Strong Completeness of Coalgebraic Modal Logics.
673-684
Electronic Edition (link) BibTeX
- Kenya Ueno:
A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints.
685-696
Electronic Edition (link) BibTeX
- Marius Zimand:
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence.
697-708
Electronic Edition (link) BibTeX
Copyright © Sat May 16 23:43:07 2009
by Michael Ley (ley@uni-trier.de)
