Skip to main content
SpringerLink
Log in

STACS 99

16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999 Proceedings

  • Conference proceedings
  • © 1999

Overview

Editors:
  1. Christoph Meinel

    1. FB IV - Informatik, Universität Trier, Trier, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Sophie Tison

    1. LIFL, Université de Lille I, Villeneuve d’Ascq Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1563)

Included in the following conference series:

Conference proceedings info: STACS 1999.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (54 papers)

  1. Front Matter

    Pages I-XIV
    Download chapter PDF

  2. Invited Talks

    1. Algorithms for Selfish Agents

      • Noam Nisan
      Pages 1-15

    2. The Reduced Genus of a Multigraph

      • Patrice Ossona de Mendez
      Pages 16-31

    3. Classifying Discrete Temporal Properties

      • Thomas Wilke
      Pages 32-46

  3. Complexity 1

    1. Circuit Complexity of Testing Square-Free Numbers

      • Anna Bernasconi, Igor Shparlinski
      Pages 47-56

    2. Relating Branching Program Size and Formula Size over the Full Binary Basis

      • Martin Sauerhoff, Ingo Wegener, Ralph Werchner
      Pages 57-67

  4. Theory of Parallel Algorithms 1

    1. Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines

      • Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, José D. P. Rolim
      Pages 68-77

    2. The Average Time Complexity to Compute Prefix Functions in Processor Networks

      • Andreas Jakoby
      Pages 78-89

  5. Complexity 2

    1. On the Hardness of Permanent

      • Jin-Yi Cai, A. Pavan, D. Sivakumar
      Pages 90-99

    2. One-Sided Versus Two-Sided Error in Probabilistic Computation

      • Harry Buhrman, Lance Fortnow
      Pages 100-109

  6. Computational Geometry

    1. An Optimal Competitive Strategy for Walking in Streets

      • Christian Icking, Rolf Klein, Elmar Langetepe
      Pages 110-120

    2. An Optimal Strategy for Searching in Unknown Streets

      • Sven Schuierer, Ines Semrau
      Pages 121-131

    3. Parallel Searching on m Rays

      • Mikael Hammar, Bengt J. Nilsson, Sven Schuierer
      Pages 132-142

  7. Complexity 3

    1. A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

      • Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick
      Pages 143-152

    2. Descriptive Complexity of Computable Sequences

      • Bruno Durand, Alexander Shen, Nikolai Vereshagin
      Pages 153-162

    3. Complexity of Some Problems in Universal Algebra

      • Clifford Bergman, Giora Slutzki
      Pages 163-172

  8. Algorithms and Data Structures 1

    1. New Branchwidth Territories

      • Ton Kloks, Jan Kratochvíl, Haiko Müller
      Pages 173-183

    2. Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions

      • Ming-Yang Kao, Andrzej Lingas, Anna Östlin
      Pages 184-196

    3. Treewidth and Minimum Fill-In of Weakly Triangulated Graphs

      • Vincent Bouchitté, Ioan Todinca
      Pages 197-206

  9. Automata and Formal Languages

    1. Decidability and Undecidability of Marked PCP

      • Vesa Halava, Mika Hirvensalo, Ronald de Wolf
      Pages 207-216
Back to top

Other volumes

  1. STACS 99

Keywords

Editors and Affiliations

  • FB IV - Informatik, Universität Trier, Trier, Germany

    Christoph Meinel

  • LIFL, Université de Lille I, Villeneuve d’Ascq Cedex, France

    Sophie Tison

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation