STACS 2004 : 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004 : proceedings
Enregistré dans:
| Collectivité auteur: | |
|---|---|
| Autres auteurs: | , |
| Format: | Livre numérique |
| Langue: | Anglais |
| Publié: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Collection: | Lecture notes in computer science
2996 |
| Sujets: | |
| Accès en ligne: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Note: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, proceedings, Volker Diekert, Michel Habib, eds, Berlin, Springer, 2004, 1 vol. (XVI-658 p.), Lecture notes in computer science, 3-540-21236-1 • STACS 2004, Texte imprimé, 9783662209097 |
Table des matières:
- Invited Lectures
- Approximation Schemes for Metric Clustering Problems
- Positional Determinacy of Infinite Games
- Structural Complexity (I)
- Individual Communication Complexity
- The Complexity of Satisfiability Problems over Finite Lattices
- Constant Width Planar Computation Characterizes ACC0
- Graph Algorithms (I)
- A Simple and Fast Approach for Solving Problems on Planar Graphs
- Sum-Multicoloring on Paths
- Matching Algorithms Are Fast in Sparse Random Graphs
- Quantum Computations
- Algebraic Results on Quantum Automata
- Quantum Identification of Boolean Oracles
- Pattern Inference and Statistics
- Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models
- A Discontinuity in Pattern Inference
- Satisfiability Constraint Satisfaction Problem
- Algorithms for SAT Based on Search in Hamming Balls
- Identifying Efficiently Solvable Cases of Max CSP
- The Complexity of Boolean Constraint Isomorphism
- Scheduling (I)
- On Minimizing the Total Weighted Tardiness on a Single Machine
- Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs
- Optimal and Online Preemptive Scheduling on Uniformly Related Machines
- Algorithms
- Parallel Prefetching and Caching Is Hard
- Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem
- Approximation Algorithms for Minimizing Average Distortion
- Networks (I)
- Digraphs Exploration with Little Memory
- Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks
- An Algorithmic View on OVSF Code Assignment
- Automata Theory and Words
- The Syntactic Graph of a Sofic Shift
- Periodicity and Unbordered Words
- Desert Automata and the Finite Substitution Problem
- Structural Complexity (II)
- Satisfiability ProblemsComplete for Deterministic Logarithmic Space
- A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number
- The Minimal Logically-Defined NP-Complete Problem
- Path Algorithms
- Solving the 2-Disjoint Paths Problem in Nearly Linear Time
- Simpler Computation of Single-Source Shortest Paths in Linear Average Time
- Cryptography
- Lattices with Many Cycles Are Dense
- Automata-Based Analysis of Recursive Cryptographic Protocols
- Networks (II)
- On Minimum Circular Arrangement
- Integral Symmetric 2-Commodity Flows
- Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks
- Logic and Formal Languages
- On the Expressiveness of Deterministic Transducers over Infinite Trees
- Definability and Regularity in Automatic Structures
- Active Context-Free Games
- Graphs Algorithms (II)
- Worst Case Performance of an Approximation Algorithm for Asymmetric TSP
- On Visibility Representation of Plane Graphs
- Topology Matters: Smoothed Competitiveness of Metrical Task Systems
- Game Theory and Complexity
- A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees
- The Plurality Problem with Three Colors
- A Measured Collapse of the Modal ?-Calculus Alternation Hierarchy
- Networks (III)
- An Information Theoretic Lower Bound for Broadcasting in Radio Networks
- A New Model for Selfish Routing
- Broadcast in the Rendezvous Model
- Structural Complexity (III)
- Time-Space Tradeoff in Derandomizing Probabilistic Logspace
- What Can be Efficiently Reduced to the K-Random Strings?
- Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms
- Scheduling (II)
- Deterministic Truthful Approximation Mechanisms for Scheduling RelatedMachines
- The Expected Competitive Ratio for Weighted Completion Time Scheduling
- Algorithmic Information
- Effective Strong Dimension in Algorithmic Information and Computational Complexity
- A Lower Bound on the Competitive Ratio of Truthful Auctions
- Errata to STACS 2003
- Errata to Analysis of the Harmonic Algorithm for Three Servers.