25. STACS 2008:
Bordeaux,
France
Susanne Albers, Pascal Weil (Eds.):
STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings.
Dagstuhl Seminar Proceedings 08001 Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008 BibTeX
Invited papers
Contributed Papers
- Pilar Albert, Elvira Mayordomo, Philippe Moser, Sylvain Perifel:
Pushdown Compression.
39-48
Electronic Edition (link) BibTeX
- Andris Ambainis:
Quantum search with variable times.
49-61
Electronic Edition (link) BibTeX
- Alexis Ballier, Bruno Durand, Emmanuel Jeandel:
Structural aspects of tilings.
61-72
Electronic Edition (link) BibTeX
- Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Veraschagin:
Limit complexities revisited.
73-84
Electronic Edition (link) BibTeX
- Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto:
Trimmed Moebius Inversion and Graphs of Bounded Degree.
85-96
Electronic Edition (link) BibTeX
- Markus Bläser, Christian Hoffmann:
On the Complexity of the Interlace Polynomial.
97-108
Electronic Edition (link) BibTeX
- Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela:
Minimizing Flow Time in the Wireless Gathering Problem.
109-120
Electronic Edition (link) BibTeX
- Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Ph. Schnoebelen, James Worrell:
On Termination for Faulty Channel Machines.
121-132
Electronic Edition (link) BibTeX
- Patrick Briest, Martin Hoefer, Piotr Krysta:
Stackelberg Network Pricing Games.
133-142
Electronic Edition (link) BibTeX
- Joshua Brody, Amit Chakrabarti:
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound.
145-156
Electronic Edition (link) BibTeX
- Venkatesan T. Chakaravarthy, Sambuddha Roy:
Finding Irrefutable Certificates for S2p via Arthur and Merlin.
157-168
Electronic Edition (link) BibTeX
- Chao Chen, Daniel Freedman:
Quantifying Homology Classes.
169-180
Electronic Edition (link) BibTeX
- Éric Colin de Verdière, Alexander Schrijver:
Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs.
181-192
Electronic Edition (link) BibTeX
- Atlas F. Cook, Carola Wenk:
Geodesic Fréchet Distance Inside a Simple Polygon.
193-204
Electronic Edition (link) BibTeX
- Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Mohammad Sohel Rahman, Tomasz Walen:
Improved Algorithms for the Range Next Value Problem and Applications.
205-216
Electronic Edition (link) BibTeX
- Mirela Damian, Robin Y. Flatland, Joseph O'Rourke, Suneeta Ramaswami:
Connecting Polygonizations via Stretches and Twangs.
217-228
Electronic Edition (link) BibTeX
- Samir Datta, Raghav Kulkarni, Sambuddha Roy:
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs.
229-240
Electronic Edition (link) BibTeX
- Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel:
Tight Bounds for Blind Search on the Integers.
241-252
Electronic Edition (link) BibTeX
- Jean-François Dufourd:
Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps.
253-264
Electronic Edition (link) BibTeX
- Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff:
Trimming of Graphs, with Application to Point Labeling.
265-276
Electronic Edition (link) BibTeX
- Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Matús Mihalák, Rajeev Raman:
Computing Minimum Spanning Trees with Uncertainty.
277-288
Electronic Edition (link) BibTeX
- Javier Esparza, Stefan Kiefer, Michael Luttenberger:
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations.
289-300
Electronic Edition (link) BibTeX
- Diana Fischer, Erich Grädel, Lukasz Kaiser:
Model Checking Games for the Quantitative µ-Calculus.
301-312
Electronic Edition (link) BibTeX
- Tobias Ganzow, Sasha Rubin:
Order-Invariant MSO is Stronger than Counting MSO in the Finite.
313-324
Electronic Edition (link) BibTeX
- Wouter Gelade, Frank Neven:
Succinctness of the Complement and Intersection of Regular Expressions.
325-336
Electronic Edition (link) BibTeX
- Christian Glasser, Heinz Schmitz, Victor L. Selivanov:
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages.
337-348
Electronic Edition (link) BibTeX
- Edith Hemaspaandra, Henning Schnoor:
On the Complexity of Elementary Modal Logics.
349-360
Electronic Edition (link) BibTeX
- Viet Tung Hoang, Wing-Kin Sung:
Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees.
361-372
Electronic Edition (link) BibTeX
- Alexander Okhotin, Artur Jez:
Complexity of solutions of equations over sets of natural numbers.
373-384
Electronic Edition (link) BibTeX
- Lukasz Kaiser, Sasha Rubin, Vince Bárány:
Cardinality and counting quantifiers on omega-automatic structures.
385-396
Electronic Edition (link) BibTeX
- Iyad A. Kanj, Michael J. Pelsmajer, Ge Xia, Marcus Schaefer:
On the Induced Matching Problem.
397-408
Electronic Edition (link) BibTeX
- Iyad A. Kanj, Ljubomir Perkovic:
On Geometric Spanners of Euclidean and Unit Disk Graphs.
409-420
Electronic Edition (link) BibTeX
- Jui-Yi Kao, Jeffrey Shallit, Zhi Xu:
The Frobenius Problem in a Free Monoid.
421-432
Electronic Edition (link) BibTeX
- Jeff Kinne, Dieter van Melkebeek:
Space Hierarchy Results for Randomized Models.
433-444
Electronic Edition (link) BibTeX
- Felix Klaedtke:
Ehrenfeucht-Fraïssé Goes Automatic for Real Addition.
445-456
Electronic Edition (link) BibTeX
- Arist Kojevnikov, Sergey I. Nikolenko:
New Combinatorial Complete One-Way Functions.
457-466
Electronic Edition (link) BibTeX
- Dietrich Kuske:
Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic.
467-478
Electronic Edition (link) BibTeX
- Sören Laue:
Geometric Set Cover and Hitting Sets for Polytopes in R³.
479-490
Electronic Edition (link) BibTeX
- Angsheng Li, Mingji Xia:
A Theory for Valiant's Matchcircuits (Extended Abstract).
491-502
Electronic Edition (link) BibTeX
- Zvi Lotker, Boaz Patt-Shamir, Dror Rawitz:
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental.
503-514
Electronic Edition (link) BibTeX
- Shachar Lovett:
Lower bounds for adaptive linearity tests.
515-526
Electronic Edition (link) BibTeX
- Pinyan Lu, Changyuan Yu:
An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines.
527-538
Electronic Edition (link) BibTeX
- Julián Mestre:
Lagrangian Relaxation and Partial Cover (Extended Abstract).
539-550
Electronic Edition (link) BibTeX
- Ulrich Meyer:
On Dynamic Breadth-First Search in External-Memory.
551-560
Electronic Edition (link) BibTeX
- Marni Mishna, Mike Zabrocki:
Analytic aspects of the shuffle product.
561-572
Electronic Edition (link) BibTeX
- Filip Murlak:
Weak index versus Borel rank.
573-584
Electronic Edition (link) BibTeX
- Jean-Eric Pin, Pedro V. Silva:
A Mahler's theorem for functions from words to integers.
585-596
Electronic Edition (link) BibTeX
- Bill Rosgen:
Distinguishing Short Quantum Computations.
597-608
Electronic Edition (link) BibTeX
- Chandan Saha:
Factoring Polynomials over Finite Fields using Balance Test.
609-620
Electronic Edition (link) BibTeX
- Jacques Sakarovitch, Rodrigo de Souza:
On the decomposition of k-valued rational relations.
621-632
Electronic Edition (link) BibTeX
- Thomas Thierauf, Fabian Wagner:
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace.
633-644
Electronic Edition (link) BibTeX
- Antti Valmari, Petri Lehtinen:
Efficient Minimization of DFAs with Partial Transition.
645-656
Electronic Edition (link) BibTeX
- Johan M. M. van Rooij, Hans L. Bodlaender:
Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set.
657-668
Electronic Edition (link) BibTeX
- Mariano Zelke:
Weighted Matching in the Semi-Streaming Model.
669-680
Electronic Edition (link) BibTeX
Copyright © Sat May 16 23:43:07 2009
by Michael Ley (ley@uni-trier.de)
