• 
  Christoph Meinel, Sophie Tison (Eds.): STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings. Springer 1999 Lecture Notes in Computer Science

Invited talks

• 
  Noam Nisan: Algorithms for Selfish Agents. 1-15
• 
  Patrice Ossona de Mendez: The Reduced Genus of a Multigraph. 16-31
• 
  Thomas Wilke: Classifying Discrete Temporal Properties. 32-46

Complexity 1

• 
  Anna Bernasconi, Igor Shparlinski: Circuit Complexity of Testing Square-Free Numbers. 47-56
• 
  Martin Sauerhoff, Ingo Wegener, Ralph Werchner: Relating Branching Program Size and Formula Size over the Full Binary Basis. 57-67

Theory of Parallel Algorithms 1

• 
  Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, José D. P. Rolim: Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines. 68-77
• 
  Andreas Jakoby: The Average Time Complexity to Compute Prefix Functions in Processor Networks. 78-89

Complexity 2

• 
  Jin-yi Cai, Aduri Pavan, D. Sivakumar: On the Hardness of Permanent. 90-99
• 
  Harry Buhrman, Lance Fortnow: One-sided Versus Two-sided Error in Probabilistic Computation. 100-109

Computational Geometry

• 
  Christian Icking, Rolf Klein, Elmar Langetepe: An Optimal Competitive Strategy for Walking in Streets. 110-120
• 
  Sven Schuierer, Ines Semrau: An Optimal Strategy for Searching in Unknown Streets. 121-131
• 
  Mikael Hammar, Bengt J. Nilsson, Sven Schuierer: Parallel Searching on m Rays. 132-142

Complexity 3

• 
  Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick: A Logical Characterisation of Linear Time on Nondeterministic Turing Machines. 143-152
• 
  Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin: Descriptive Complexity of Computable Sequences. 153-162
• 
  Clifford Bergman, Giora Slutzki: Complexity of Some Problems in Universal Algebra. 163-172

Algorithms and Data Structures 1

• 
  Ton Kloks, Jan Kratochvíl, Haiko Müller: New Branchwidth Territories. 173-183
• 
  Ming-Yang Kao, Andrzej Lingas, Anna Östlin: Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions. 184-196
• 
  Vincent Bouchitté, Ioan Todinca: Treewidth and Minimum Fill-in of Weakly Triangulated Graphs. 197-206

Automata and Formal Languages

• 
  Vesa Halava, Mika Hirvensalo, Ronald de Wolf: Decidability and Undecidability of Marked PCP. 207-216
• 
  John Michael Robson, Volker Diekert: On Quadratic Word Equations. 217-226
• 
  Daniel Kirsten: Some Undecidability Results Related to the Star Problem in Trace Monoids. 227-236

Algorithms and Data Structures 2

• 
  Gunnar Andersson: An Approximation Algorithm for Max p-Section. 237-247
• 
  Dieter Kratsch, Lorna Stewart: Approximating Bandwidth by Mixing Layouts of Interval Graphs. 248-258
• 
  Robert Preis: Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. 259-269

Complexity 4

• 
  Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries. 269-280
• 
  Vikraman Arvind, Jacobo Torán: Sparse Sets, Approximable Sets, and Parallel Queries to NP. 281-290

Algorithms and Data Structures 3

• 
  Jop F. Sibeyn: External Selection. 291-301
• 
  Timm Ahrendt: Fast Computations of the Exponential Function. 302-312

Verification

• 
  Maciej Koutny, Giuseppe Pappalardo: A Model of Behaviour Abstraction for Communicating Processes. 313-322
• 
  Ahmed Bouajjani, Richard Mayr: Model Checking Lossy Vector Addition Systems. 323-333

Algorithms and Data Structures 4

• 
  Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang: Constructing Light Spanning Trees with Small Routing Cost. 334-344
• 
  Matti Nykänen, Esko Ukkonen: Finding Paths with the Right Cost. 345-355

Complexity 5

• 
  Mario Szegedy: In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? 356-361
• 
  Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen: Lower Bounds for Dynamic Algebraic Problems. 362-372
• 
  Lars Engebretsen: An Explicit Lower Bound for TSP with Distances One and Two. 373-382

Theory of Parallel Algorithms 2

• 
  Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk: Scheduling Dynamic Graphs. 383-392
• 
  William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou: Supporting Increment and Decrement Operations in Balancing Networks. 393-403
• 
  Elias Koutsoupias, Christos H. Papadimitriou: Worst-case Equilibria. 404-413

Algorithmic Learning

• 
  Rüdiger Reischuk, Thomas Zeugmann: A Complete and Tight Average-Case Analysis of Learning Monomials. 414-423
• 
  John Case, Keh-Jiann Chen, Sanjay Jain: Costs of General Purpose Learning. 424-433
• 
  Rainer Schuler: Universal Distributions and Time-Bounded Kolmogorov Complexity. 434-443

Logic in Computer Science

• 
  Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer: The Descriptive Complexity Approach to LOGCFL. 444-454
• 
  Orna Kupferman, Moshe Y. Vardi: The Weakness of Self-Complementation. 455-466
• 
  Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino: On the Difference of Horn Theories. 467-477

Complexity 6

• 
  Mark Ettinger, Peter Høyer: On Quantum Algorithms for Noncommutative Hidden Subgroups. 478-487
• 
  Martin Sauerhoff: On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions. 488-499
• 
  Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson: How to Forget a Secret. 500-509

Logic in Computer Science 2

• 
  Markus Müller-Olm: A Modal Fixpoint Logic with Chop. 510-520
• 
  Rana Barua, Suman Roy, Zhou Chaochen: Completeness of Neighbourhood Logic. 521-530
• 
  Martin Otto: Eliminating Recursion in the µ-Calculus. 531-540

Complexity 7

• 
  Jochen Meßner: On Optimal Algorithms and Optimal Proof Systems. 541-550
• 
  Juan Luis Esteban, Jacobo Torán: Space Bounds for Resolution. 551-560

Algorithms and Data Structures 5

• 
  Rolf Niedermeier, Peter Rossmanith: Upper Bounds for Vertex Cover Further Improved. 561-570
• 
  Marco Riedel: Online Matching for Scheduling Problems. 571-580