default search action
16th STACS 1999: Trier, Germany
- Christoph Meinel, Sophie Tison
:
STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings. Lecture Notes in Computer Science 1563, Springer 1999
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 E. 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
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
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
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
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
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
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-12-13 19:00 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: