STACS 2004 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings / edited by Volker Diekert, Michel Habib.

Saved in:

Bibliographic Details
Corporate Author:	SpringerLink (Online service)
Other Authors:	Diekert, Volker (Editor), Habib, Michel (Editor)
Format:	eBook
Language:	English
Published:	Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2004.
Edition:	1st ed. 2004.
Series:	Lecture Notes in Computer Science, 2996 Springer eBook Collection.
Subjects:	Computers. Data structures (Computer science). Algorithms. Computer logic. Mathematical logic. Electronic resources (E-books)
Online Access:	Click to view e-book
Holy Cross Note:	Loaded electronically. Electronic access restricted to members of the Holy Cross Community.

Table of Contents:

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.

STACS 2004 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings / edited by Volker Diekert, Michel Habib.

Similar Items