STACS 2004 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004. Proceedings /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | , |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg,
2004.
|
| Σειρά: | Lecture Notes in Computer Science,
2996 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- 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 Problems Complete 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 Related Machines
- 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.
