Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2004

STACS 2004

21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings

Editors:

  1. Volker Diekert

    1. Universität Stuttgart, FMI, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Michel Habib

    1. LIAFA and the University of Paris 7, Denis Diderot,  

    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 2996)

Conference series link(s): STACS: Annual Symposium on Theoretical Aspects of Computer Science

Conference proceedings info: STACS 2004.

Sections

Buy it now

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

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

Table of contents (57 papers)

  1. Front Matter

    PDF

  2. Invited Lectures

    2. Positional Determinacy of Infinite Games

      • Erich Grädel
      Pages 4-18

  3. Structural Complexity (I)

    1. Individual Communication Complexity

      • Harry Buhrman, Hartmut Klauck, Nikolai Vereshchagin, Paul Vitányi
      Pages 19-30

    3. Constant Width Planar Computation Characterizes ACC0

      • Kristoffer Arnsfelt Hansen
      Pages 44-55

  4. Graph Algorithms (I)

    1. A Simple and Fast Approach for Solving Problems on Planar Graphs

      • Fedor V. Fomin, Dimtirios M. Thilikos
      Pages 56-67

    2. Sum-Multicoloring on Paths

      • Annamária Kovács
      Pages 68-80

    3. Matching Algorithms Are Fast in Sparse Random Graphs

      • Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
      Pages 81-92

  5. Quantum Computations

    1. Algebraic Results on Quantum Automata

      • Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Ķikusts, Mark Mercer, Denis Thérien
      Pages 93-104

    2. Quantum Identification of Boolean Oracles

      • Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita
      Pages 105-116

  6. Pattern Inference and Statistics

    1. Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models

      • Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati
      Pages 117-128

    2. A Discontinuity in Pattern Inference

      • Daniel Reidenbach
      Pages 129-140

  7. Satisfiability – Constraint Satisfaction Problem

    1. Algorithms for SAT Based on Search in Hamming Balls

      • Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert
      Pages 141-151

    2. Identifying Efficiently Solvable Cases of Max CSP

      • David Cohen, Martin Cooper, Peter Jeavons, Andrei Krokhin
      Pages 152-163

    3. The Complexity of Boolean Constraint Isomorphism

      • Elmar Böhler, Edith Hemaspaandra, Steffen Reith, Heribert Vollmer
      Pages 164-175

  8. Scheduling (I)

    1. On Minimizing the Total Weighted Tardiness on a Single Machine

      • Stavros G. Kolliopoulos, George Steiner
      Pages 176-186

    2. Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs

      • Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi et al.
      Pages 187-198

    3. Optimal and Online Preemptive Scheduling on Uniformly Related Machines

      • Tomáš Ebenlendr, Jiří Sgall
      Pages 199-210

  9. Algorithms

    1. Parallel Prefetching and Caching Is Hard

      • Christoph Ambühl, Birgitta Weber
      Pages 211-221
Back to top

Other Volumes

  1. STACS 2004

Back to top

Keywords

Back to top

Editors and Affiliations

  • Universität Stuttgart, FMI, Germany

    Volker Diekert

  • LIAFA and the University of Paris 7, Denis Diderot,  

    Michel Habib

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

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

Search

Navigation