25th International Symposium on Theoretical Aspects of Computer Science

STACS 2008

Accepted papers

  • P. Albert, E. Mayordomo, P. Moser and S. Perifel,
    Pushdown Compression.
  • A. Ambainis,
    Quantum search with variable times.
  • A. Ballier, B. Durand and E. Jeandel,
    Structural aspects of tilings.
  • L. Bienvenu, A. Muchnik, A. Shen and N. Vereshchagin,
    Limit complexities revisited.
  • A. Bjorklund, T. Husfeldt, P. Kaski and M. Koivisto,
    Trimmed Moebius Inversion and Graphs of Bounded Degree.
  • M. Bläser and C. Hoffmann,
    On the Complexity of the Interlace Polynomial.
  • V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela and L. Stougie,
    Minimizing Flow Time in the Wireless Gathering Problem.
  • P. Bouyer, N. Markey, J. Ouaknine, P. Schnoebelen and J. Worrell,
    On Termination for Faulty Channel Machines.
  • P. Briest, M. Hoefer and P. Krysta,
    Stackelberg Network Pricing Games.
  • J. Brody and A. Chakrabarti,
    Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound.
  • V. Chakaravarthy and S. Roy ,
    Finding Irrefutable Certificates for S2p via Arthur and Merlin.
  • C. Chen and D. Freedman,
    Quantifying Homology Classes.
  • É. Colin de Verdière and A. Schrijver,
    Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs.
  • A. F. Cook IV and C. Wenk,
    Geodesic Fréchet Distance Inside a Simple Polygon.
  • M. Crochemore, C. Iliopoulos, M. Kubica, M. S. Rahman and T. Walen,
    Improved Algorithms for the Range Next Value Problem and Applications.
  • M. Damian, R. Flatland, J. O'Rourke and S. Ramaswami,
    Connecting Polygonizations via Stretches and Twangs.
  • S. Datta, R. Kulkarni and S. Roy,
    Deterministically Isolating a Matching in Bipartite Planar Graphs.
  • M. Dietzfelbinger, J. E. Rowe, I. Wegener and P. Woelfel,
    Tight Bounds for Blind Search on the Integers.
  • J.-F. Dufourd,
    Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps.
  • T. Erlebach, T. Hagerup, K. Jansen, M. Minzlaff and A. Wolff,
    Trimming of Graphs, with Application to Point Labeling.
  • T. Erlebach, M. Hoffmann, D. Krizanc, M. Mihalak and R. Raman,
    Computing Minimum Spanning Trees with Uncertainty.
  • J. Esparza, S. Kiefer and M. Luttenberger,
    Convergence Thresholds of Newton's Method for Monotone Polynomial Equations.
  • T. Ganzow and S. Rubin,
    Order-Invariant MSO is Stronger than Counting MSO in the Finite.
  • W. Gelade and F. Neven,
    Succinctness of the complement and intersection of regular expressions.
  • C. Glaßer, H. Schmitz and V. Selivanov,
    Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages.
  • E. Hemaspaandra and H. Schnoor,
    On the Complexity of Elementary Modal Logics.
  • V. T. Hoang and W.-K. Sung,
    Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees.
  • A. Jez and A. Okhotin,
    Complexity of solutions of equations over sets of natural numbers.
  • L. Kaiser, V. Barany and S. Rubin,
    Cardinality and counting quantifiers on omega-automatic structures.
  • L. Kaiser, D. Fischer and E. Graedel,
    Model Checking Games for the Quantitative mu-Calculus.
  • I. Kanj, M. J. Pelsmajer, M. Schaefer and G. Xia,
    On the Induced Matching Problem.
  • I. Kanj and L. Perkovic,
    On Geometric Spanners of Euclidean and Unit Disk Graphs.
  • J.-Y. Kao, J. Shallit and Z. Xu,
    The Frobenius Problem in a Free Monoid.
  • J. Kinne and D. van Melkebeek,
    Space Hierarchy Results for Randomized Models.
  • F. Klaedtke,
    Ehrenfeucht-Fraïssé Goes Automatic for Real Addition.
  • A. Kojevnikov and S. Nikolenko,
    New Combinatorial Complete One-Way Functions.
  • D. Kuske,
    Compatibility of Shelah and Stupp's and Muchnik's iterations with fragments of monadic second order logic.
  • S. Laue,
    Geometric Set Cover and Hitting Sets for Polytopes in R3.
  • A. Li and M. Xia,
    A Theory for Valiant's Matchcircuits.
  • Z. Lotker, B. Patt-Shamir and D. Rawitz,
    Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental.
  • S. Lovett,
    Lower bounds for adaptive linearity tests.
  • P. Lu and C. Yu,
    An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines.
  • J. Mestre,
    Lagrangian Relaxation and Partial Cover.
  • U. Meyer,
    On Dynamic Breadth-First Search in External-Memory.
  • M. Mishna and M. Zabrocki,
    Analytic aspects of the shuffle product.
  • F. Murlak,
    Weak index versus Borel rank.
  • J.-É. Pin and P. Silva,
    A Mahler's theorem for functions from words to integers.
  • B. Rosgen,
    Distinguishing Short Quantum Computations.
  • C. Saha,
    Factoring Polynomials over Finite Fields using Balance Test.
  • J. Sakarovitch and R. de Souza,
    On the decomposition of k-valued rational relations.
  • T. Thierauf and F. Wagner,
    The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace.
  • A. Valmari and P. Lehtinen,
    Efficient Minimization of DFAs with Partial Transition Functions.
  • J. van Rooij and H. Bodlaender,
    Design by Measure and Conquer - A Faster Exact Algorithm for Dominating Set.
  • M. Zelke,
    Weighted Matching in the Semi-Streaming Model.