default search action
28th STACS 2011: Dortmund, Germany
- Thomas Schwentick, Christoph Dürr:
28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany. LIPIcs 9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2011, ISBN 978-3-939897-25-5 - Thomas Schwentick, Christoph Dürr:
Frontmatter, Table of Contents, Preface, Conference Organization.
Invited Papers
- Susanne Albers:
Algorithms for Dynamic Speed Scaling. 1-11 - Markus Aschinger, Conrad Drescher, Georg Gottlob
, Peter Jeavons, Evgenij Thorstensen:
Structural Decomposition Methods and What They are Good For. 12-28 - Hubert Comon-Lundh, Véronique Cortier:
How to prove security of communication protocols? A discussion on the soundness of formal models w.r.t. computational ones. 29-44
Distributed and Fault-Tolerant Computing
- Saverio Caminiti, Irene Finocchi
Local dependency dynamic programming in the presence of memory faults. 45-56 - George Giakkoupis:
Tight bounds for rumor spreading in graphs of a given conductance. 57-68 - Liah Kor, Amos Korman, David Peleg:
Tight Bounds For Distributed MST Verification. 69-80
Data Words and Data Trees
- Luc Segoufin, Szymon Torunczyk
Automata based verification over linearly ordered data domains. 81-92 - Diego Figueira, Luc Segoufin:
Bottom-up automata on data trees and vertical XPath. 93-104 - Mikolaj Bojanczyk:
Data Monoids. 105-116
Cuts and Flows
- Haim Kaplan, Yahav Nussbaum:
Minimum s-t cut in undirected planar graphs when the source and the sink are close. 117-128 - Petr Kolman
Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing. 129-140
Computational Geometry
- Jiun-Jie Wang, Xin He:
Compact Visibility Representation of Plane Graphs. 141-152 - Jérémie Chalopin, Shantanu Das, Yann Disser, Matús Mihalák, Peter Widmayer:
Telling convex from reflex allows to map a polygon. 153-164
Kernelization
- Hans L. Bodlaender
Cross-Composition: A New Technique for Kernelization Lower Bounds. 165-176 - Bart M. P. Jansen, Hans L. Bodlaender
Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter. 177-188 - Fedor V. Fomin
Hitting forbidden minors: Approximation and Kernelization. 189-200
Morphism, Words, Bio Computing
- Erik D. Demaine, Matthew J. Patitz
Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract). 201-212 - Dominik D. Freydenberger
Weakly Unambiguous Morphisms. 213-224 - Francine Blanchet-Sadri, John Lensmire:
On Minimal Sturmian Partial Words. 225-236
SAT & CSP
- Timon Hertli, Robin A. Moser, Dominik Scheder
Improving PPSZ for 3-SAT using Critical Variables. 237-248 - Heng Guo, Sangxia Huang, Pinyan Lu
The Complexity of Weighted Boolean #CSP Modulo k. 249-260 - Martin E. Dyer
The #CSP Dichotomy is Decidable. 261-272
Cellular Automata
- Alex Borello, Gaétan Richard, Véronique Terrier:
A speed-up of oblivious multi-head finite automata by cellular automata. 273-283 - Nazim Fatès
Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision. 284-295 - Ana Busic
Probabilistic cellular automata, invariant measures, and perfect sampling. 296-307
Clustering and Learning
- Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, Christian Sohler
Analysis of Agglomerative Clustering. 308-319 - John Case, Timo Kötzing:
Measuring Learning Complexity with Criteria Epitomizers. 320-331 - Howard J. Karloff, Flip Korn, Konstantin Makarychev, Yuval Rabani:
On Parsimonious Explanations For 2-D Tree- and Linearly-Ordered Data. 332-343
Logic
- Balder ten Cate, Luc Segoufin:
Unary negation. 344-355 - Jakub Kallas, Manfred Kufleitner
First-order Fragments with Successor over Infinite Words. 356-367 - Martin Mundhenk, Felix Weiß:
The model checking problem for propositional intuitionistic logic with one variable is AC^1-complete. 368-379
Scheduling 1
- Alejandro López-Ortiz, Claude-Guy Quimper
A Fast Algorithm for Multi-Machine Scheduling Problems with Jobs of Equal Processing Times. 380-391 - Sze-Hang Chan, Tak Wah Lam
Scheduling for Weighted Flow Time and Energy with Rejection Penalty. 392-403
Graph Decomposition
- Robert Ganian
Clique-width: When Hard Does Not Mean Impossible. 404-415 - Dariusz Dereniowski
From Pathwidth to Connected Pathwidth. 416-427
Streaming
- Andrew McGregor, Atri Rudra, Steve Uurtamo:
Polynomial Fitting of Data Streams with Applications to Codeword Testing. 428-439 - Jonathan A. Kelner, Alex Levin:
Spectral Sparsification in the Semi-Streaming Setting. 440-451
Recursion Theory
- Laurent Bienvenu, Wolfgang Merkle, André Nies
Solovay functions and K-triviality. 452-463 - Andrey Yu. Rumyantsev:
Everywhere complex sequences and the probabilistic method. 464-471
Scheduling 2
- Magnús M. Halldórsson
Online Scheduling with Interval Conflicts. 472-483 - Christian Eggermont, Alexander Schrijver, Gerhard J. Woeginger:
Analysis of multi-stage open shop processing systems. 484-494
Regular Expressions
- Stefan Gulan:
Graphs Encoded by Regular Expressions. 495-506 - Dominik D. Freydenberger
Extended Regular Expressions: Succinctness and Decidability. 507-518
Graph Algorithms
- Maxim A. Babenko, Alexey Gusakov:
New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs. 519-530 - Antonios Antoniadis, Falk Hüffner
Balanced Interval Coloring. 531-542
Algebra & Complexity
- Bruno Grenet
Symmetric Determinantal Representation of Weakly-Skew Circuits. 543-554 - Markus Bläser, Christian Engels
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals. 555-566
Complexity of Graph & Group Problems
- Youming Qiao
On Isomorphism Testing of Groups with Normal Hall Subgroups. 567-578 - Samir Datta
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. 579-590 - George B. Mertzios:
The Recognition of Triangle Graphs. 591-602
Versification
- Pawel Parys:
Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. 603-614 - Orna Kupferman, Yoad Lustig, Moshe Y. Vardi, Mihalis Yannakakis:
Temporal Synthesis for Bounded Systems and Environments. 615-626 - Denis Kuperberg:
Linear temporal logic for regular cost functions. 627-636
Geometry and Complexity
- Adrian Dumitrescu, André Schulz, Adam Sheffer, Csaba D. Tóth:
Bounds on the maximum multiplicity of some common geometric graphs. 637-648 - Christian Knauer, Hans Raj Tiwary
On the computational complexity of Ham-Sandwich cuts, Helly sets, and related problems. 649-660
Query Complexity
- Andrew M. Childs, Robin Kothari
Quantum query complexity of minor-closed graph properties. 661-672 - Anna Gál, Andrew Mills:
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length. 673-684
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-22 19:32 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: