28. STACS 2011: Dortmund, Germany

• 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, Emanuele G. Fusco:
  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, Christian Scheideler:
  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, Bart M. P. Jansen, Stefan Kratsch:
  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, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, Saket Saurabh:
  Hitting forbidden minors: Approximation and Kernelization. 189-200
  

Morphism, Words, Bio Computing

• Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers:
  Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract). 201-212
  
• Dominik D. Freydenberger, Hossein Nevisi, Daniel Reidenbach:
  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, Mingji Xia:
  The Complexity of Weighted Boolean #CSP Modulo k. 249-260
  
• Martin E. Dyer, David Richerby:
  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, Jean Mairesse, Irene Marcovici:
  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, Alexander Lauser:
  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, Lap-Kei Lee:
  Scheduling for Weighted Flow Time and Energy with Rejection Penalty. 392-403
  

Graph Decomposition

• Robert Ganian, Petr Hlinený, Jan Obdrzálek:
  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, Boaz Patt-Shamir, Dror Rawitz:
  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, Pascal Lenzner, Carsten Moldenhauer, Alexander Souza:
  Balanced Interval Coloring. 531-542
  

Algebra & Complexity

• Bruno Grenet, Erich Kaltofen, Pascal Koiran, Natacha Portier:
  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, Jayalal M. N. Sarma, Bangsheng Tang:
  On Isomorphism Testing of Groups with Normal Hall Subgroups. 567-578
  
• Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. Variyam Vinodchandran:
  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, Daniel Werner:
  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
  

Last update Thu May 24 04:44:46 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page