STACS 2011 March 10-12, 2011, Dortmund, Germany

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)



Thomas Schwentick and Christoph Dürr (Eds.)
ISBN 978-3-939897-25-5, LIPICS Vol. 9 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 28 MB)
Search Publication Server


Authors
  • Ackermann, Marcel R.
  • Albers, Susanne
  • Antoniadis, Antonios
  • Aschinger, Markus
  • Babenko, Maxim
  • Bienvenu, Laurent
  • Blaeser, Markus
  • Blanchet-Sadri, Francine
  • Bloemer, Johannes
  • Bodlaender, Hans L.
  • Bojanczyk, Mikolaj
  • Borelllo, Alex
  • Busic, Ana
  • Caminiti, Saverio
  • Case, John
  • Chalopin, Jeremie
  • Chan, Sze-Hang
  • Childs, Andrew M.
  • Comon-Lundh, Hubert
  • Cortier, Véronique
  • Dürr, Christoph
  • Das, Shantanu
  • Datta, Samir
  • Demaine, Erik D.
  • Dereniowski, Dariusz
  • Disser, Yann
  • Drescher, Conrad
  • Dumitrescu, Adrian
  • Dyer, Martin
  • Eggermont, Christian E.J.
  • Engels, Christian
  • Fates, Nazim
  • Figueira, Diego
  • Finocchi, Irene
  • Fomin, Fedor V.
  • Freydenberger, Dominik D.
  • Fusco, Emanuele G.
  • Gal, Anna
  • Ganian, Robert
  • Giakkoupis, George
  • Gottlob, Georg
  • Grenet, Bruno
  • Gulan, Stefan
  • Guo, Heng
  • Gusakov, Alexey
  • Halldorsson, Magnus M.
  • He, Xin
  • Hertli, Timon
  • Hlineny, Petr
  • Huang, Sangxia
  • Hueffner, Falk
  • Jansen, Bart M. P.
  • Jeavons, Peter
  • Kallas, Jakub
  • Kaltofen, Erich L.
  • Kaplan, Haim
  • Karloff, Howard
  • Kelner, Jonathan A.
  • Knauer, Christian
  • Koetzing, Timo
  • Koiran, Pascal
  • Kolman, Petr
  • Kor, Liah
  • Korman, Amos
  • Korn, Flip
  • Kothari, Robin
  • Kratsch, Stefan
  • Kufleitner, Manfred
  • Kulkarni, Raghav
  • Kuntze, Daniel
  • Kuperberg, Denis
  • Kupferman, Orna
  • Lam, Tak-Wah
  • Lauser, Alexander
  • Lee, Lap-Kei
  • Lensmire, John
  • Lenzner, Pascal
  • Levin, Alex
  • Lokshtanov, Daniel
  • Lopez-Ortiz, Alejandro
  • Lu, Pinyan
  • Lustig, Yoad
  • Mairesse, Jean
  • Makarychev, Konstantin
  • Marcovici, Irene
  • McGregor, Andrew
  • Merkle, Wolfgang
  • Mertzios, George B.
  • Mihalak, Matus
  • Mills, Andrew
  • Misra, Neeldhara
  • Moldenhauer, Carsten
  • Moser, Robin A.
  • Mundhenk, Martin
  • Nevisi, Hossein
  • Nies, Andre
  • Nussbaum, Yahav
  • Obdrzalek, Jan
  • Parys, Pawel
  • Patitz, Matthew J.
  • Patt-Shamir, Boaz
  • Peleg, David
  • Philip, Geevarghese
  • Portier, Natacha
  • Qiao, Youming
  • Quimper, Claude-Guy
  • Rabani, Yuval
  • Rawitz, Dror
  • Reidenbach, Daniel
  • Richard, Gaetan
  • Richerby, David
  • Rudra, Atri
  • Rumyantsev, Andrey Yu.
  • Sarma M.N., Jayalal
  • Saurabh, Saket
  • Scheder, Dominik
  • Scheideler, Christian
  • Schrijver, Alexander
  • Schulz, Andre
  • Schweller, Robert T.
  • Schwentick, Thomas
  • Segoufin, Luc
  • Sheffer, Adam
  • Sohler, Christian
  • Souza, Alexander
  • Summers, Scott M.
  • Tang, Bangsheng
  • ten Cate, Balder
  • Terrier, Veronique
  • Tewari, Raghunath
  • Thorstensen, Evgenij
  • Tiwary, Hans Raj
  • Torunczyk, Szymon
  • Toth, Csaba D.
  • Uurtamo, Steve
  • Vardi, Moshe Y.
  • Vinodchandran, N. Variyam
  • Wang, Jiun-Jie
  • Weiß, Felix
  • Werner, Daniel
  • Widmayer, Peter
  • Woeginger, Gerhard J.
  • Xia, Mingji
  • Yannakakis, Mihalis

  •   
    Frontmatter, Table of Contents, Preface, Conference Organization
    Authors: Schwentick, Thomas ; Dürr, Christoph

    Abstract | Document (526 KB) | BibTeX

    Algorithms for Dynamic Speed Scaling
    Authors: Albers, Susanne

    Abstract | Document (531 KB) | BibTeX

    Structural Decomposition Methods and What They are Good For
    Authors: Aschinger, Markus ; Drescher, Conrad ; Gottlob, Georg ; Jeavons, Peter ; Thorstensen, Evgenij

    Abstract | Document (815 KB) | BibTeX

    How to prove security of communication protocols? A discussion on the soundness of formal models w.r.t. computational ones.
    Authors: Comon-Lundh, Hubert ; Cortier, Véronique

    Abstract | Document (618 KB) | BibTeX

    Local dependency dynamic programming in the presence of memory faults
    Authors: Caminiti, Saverio ; Finocchi, Irene ; Fusco, Emanuele G.

    Abstract | Document (694 KB) | BibTeX

    Tight bounds for rumor spreading in graphs of a given conductance
    Authors: Giakkoupis, George

    Abstract | Document (627 KB) | BibTeX

    Tight Bounds For Distributed MST Verification
    Authors: Kor, Liah ; Korman, Amos ; Peleg, David

    Abstract | Document (685 KB) | BibTeX

    Automata based verification over linearly ordered data domains
    Authors: Segoufin, Luc ; Torunczyk, Szymon

    Abstract | Document (613 KB) | BibTeX

    Bottom-up automata on data trees and vertical XPath
    Authors: Figueira, Diego ; Segoufin, Luc

    Abstract | Document (2,056 KB) | BibTeX

    Data Monoids
    Authors: Bojanczyk, Mikolaj

    Abstract | Document (550 KB) | BibTeX

    Minimum s-t cut in undirected planar graphs when the source and the sink are close
    Authors: Kaplan, Haim ; Nussbaum, Yahav

    Abstract | Document (680 KB) | BibTeX

    Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing
    Authors: Kolman, Petr ; Scheideler, Christian

    Abstract | Document (629 KB) | BibTeX

    Compact Visibility Representation of Plane Graphs
    Authors: Wang, Jiun-Jie ; He, Xin

    Abstract | Document (661 KB) | BibTeX

    Telling convex from reflex allows to map a polygon
    Authors: Chalopin, Jeremie ; Das, Shantanu ; Disser, Yann ; Mihalak, Matus ; Widmayer, Peter

    Abstract | Document (726 KB) | BibTeX

    Cross-Composition: A New Technique for Kernelization Lower Bounds
    Authors: Bodlaender, Hans L. ; Jansen, Bart M. P. ; Kratsch, Stefan

    Abstract | Document (653 KB) | BibTeX

    Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter
    Authors: Jansen, Bart M. P. ; Bodlaender, Hans L.

    Abstract | Document (648 KB) | BibTeX

    Hitting forbidden minors: Approximation and Kernelization
    Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Misra, Neeldhara ; Philip, Geevarghese ; Saurabh, Saket

    Abstract | Document (3,041 KB) | BibTeX

    Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract)
    Authors: Demaine, Erik D. ; Patitz, Matthew J. ; Schweller, Robert T. ; Summers, Scott M.

    Abstract | Document (834 KB) | BibTeX

    Weakly Unambiguous Morphisms
    Authors: Freydenberger, Dominik D. ; Nevisi, Hossein ; Reidenbach, Daniel

    Abstract | Document (644 KB) | BibTeX

    On Minimal Sturmian Partial Words
    Authors: Blanchet-Sadri, Francine ; Lensmire, John

    Abstract | Document (760 KB) | BibTeX

    Improving PPSZ for 3-SAT using Critical Variables
    Authors: Hertli, Timon ; Moser, Robin A. ; Scheder, Dominik

    Abstract | Document (704 KB) | BibTeX

    The Complexity of Weighted Boolean #CSP Modulo k
    Authors: Guo, Heng ; Huang, Sangxia ; Lu, Pinyan ; Xia, Mingji

    Abstract | Document (696 KB) | BibTeX

    The #CSP Dichotomy is Decidable
    Authors: Dyer, Martin ; Richerby, David

    Abstract | Document (622 KB) | BibTeX

    A speed-up of oblivious multi-head finite automata by cellular automata
    Authors: Borelllo, Alex ; Richard, Gaetan ; Terrier, Veronique

    Abstract | Document (1,238 KB) | BibTeX

    Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
    Authors: Fates, Nazim

    Abstract | Document (681 KB) | BibTeX

    Probabilistic cellular automata, invariant measures, and perfect sampling
    Authors: Busic, Ana ; Mairesse, Jean ; Marcovici, Irene

    Abstract | Document (819 KB) | BibTeX

    Analysis of Agglomerative Clustering
    Authors: Ackermann, Marcel R. ; Bloemer, Johannes ; Kuntze, Daniel ; Sohler, Christian

    Abstract | Document (757 KB) | BibTeX

    Measuring Learning Complexity with Criteria Epitomizers
    Authors: Case, John ; Koetzing, Timo

    Abstract | Document (741 KB) | BibTeX

    On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data
    Authors: Karloff, Howard ; Korn, Flip ; Makarychev, Konstantin ; Rabani, Yuval

    Abstract | Document (621 KB) | BibTeX

    Unary negation
    Authors: ten Cate, Balder ; Segoufin, Luc

    Abstract | Document (686 KB) | BibTeX

    First-order Fragments with Successor over Infinite Words
    Authors: Kallas, Jakub ; Kufleitner, Manfred ; Lauser, Alexander

    Abstract | Document (720 KB) | BibTeX

    The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete
    Authors: Mundhenk, Martin ; Weiß, Felix

    Abstract | Document (817 KB) | BibTeX

    A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times
    Authors: Lopez-Ortiz, Alejandro ; Quimper, Claude-Guy

    Abstract | Document (788 KB) | BibTeX

    Scheduling for Weighted Flow Time and Energy with Rejection Penalty
    Authors: Chan, Sze-Hang ; Lam, Tak-Wah ; Lee, Lap-Kei

    Abstract | Document (656 KB) | BibTeX

    Clique-width: When Hard Does Not Mean Impossible
    Authors: Ganian, Robert ; Hlineny, Petr ; Obdrzalek, Jan

    Abstract | Document (739 KB) | BibTeX

    From Pathwidth to Connected Pathwidth
    Authors: Dereniowski, Dariusz

    Abstract | Document (772 KB) | BibTeX

    Polynomial Fitting of Data Streams with Applications to Codeword Testing
    Authors: McGregor, Andrew ; Rudra, Atri ; Uurtamo, Steve

    Abstract | Document (626 KB) | BibTeX

    Spectral Sparsification in the Semi-Streaming Setting
    Authors: Kelner, Jonathan A. ; Levin, Alex

    Abstract | Document (573 KB) | BibTeX

    Solovay functions and K-triviality
    Authors: Bienvenu, Laurent ; Merkle, Wolfgang ; Nies, Andre

    Abstract | Document (619 KB) | BibTeX

    Everywhere complex sequences and the probabilistic method
    Authors: Rumyantsev, Andrey Yu.

    Abstract | Document (542 KB) | BibTeX

    Online Scheduling with Interval Conflicts
    Authors: Halldorsson, Magnus M. ; Patt-Shamir, Boaz ; Rawitz, Dror

    Abstract | Document (669 KB) | BibTeX

    Analysis of multi-stage open shop processing systems
    Authors: Eggermont, Christian E.J. ; Schrijver, Alexander ; Woeginger, Gerhard J.

    Abstract | Document (556 KB) | BibTeX

    Graphs Encoded by Regular Expressions
    Authors: Gulan, Stefan

    Abstract | Document (688 KB) | BibTeX

    Extended Regular Expressions: Succinctness and Decidability
    Authors: Freydenberger, Dominik D.

    Abstract | Document (646 KB) | BibTeX

    New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs
    Authors: Babenko, Maxim ; Gusakov, Alexey

    Abstract | Document (612 KB) | BibTeX

    Balanced Interval Coloring
    Authors: Antoniadis, Antonios ; Hueffner, Falk ; Lenzner, Pascal ; Moldenhauer, Carsten ; Souza, Alexander

    Abstract | Document (565 KB) | BibTeX

    Symmetric Determinantal Representation of Weakly-Skew Circuits
    Authors: Grenet, Bruno ; Kaltofen, Erich L. ; Koiran, Pascal ; Portier, Natacha

    Abstract | Document (721 KB) | BibTeX

    Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals
    Authors: Blaeser, Markus ; Engels, Christian

    Abstract | Document (620 KB) | BibTeX

    On Isomorphism Testing of Groups with Normal Hall Subgroups
    Authors: Qiao, Youming ; Sarma M.N., Jayalal ; Tang, Bangsheng

    Abstract | Document (691 KB) | BibTeX

    Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
    Authors: Datta, Samir ; Kulkarni, Raghav ; Tewari, Raghunath ; Vinodchandran, N. Variyam

    Abstract | Document (703 KB) | BibTeX

    The Recognition of Triangle Graphs
    Authors: Mertzios, George B.

    Abstract | Document (744 KB) | BibTeX

    Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata
    Authors: Parys, Pawel

    Abstract | Document (568 KB) | BibTeX

    Temporal Synthesis for Bounded Systems and Environments
    Authors: Kupferman, Orna ; Lustig, Yoad ; Vardi, Moshe Y. ; Yannakakis, Mihalis

    Abstract | Document (448 KB) | BibTeX

    Linear temporal logic for regular cost functions
    Authors: Kuperberg, Denis

    Abstract | Document (146 KB) | BibTeX

    Bounds on the maximum multiplicity of some common geometric graphs
    Authors: Dumitrescu, Adrian ; Schulz, Andre ; Sheffer, Adam ; Toth, Csaba D.

    Abstract | Document (813 KB) | BibTeX

    On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems
    Authors: Knauer, Christian ; Tiwary, Hans Raj ; Werner, Daniel

    Abstract | Document (661 KB) | BibTeX

    Quantum query complexity of minor-closed graph properties
    Authors: Childs, Andrew M. ; Kothari, Robin

    Abstract | Document (843 KB) | BibTeX

    Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length
    Authors: Gal, Anna ; Mills, Andrew

    Abstract | Document (584 KB) | BibTeX

    Index of Authors
    Authors: Schwentick, Thomas ; Dürr, Christoph

    Abstract | Document (66 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI