![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
21st STACS 2004: Montpellier, France
- Volker Diekert, Michel Habib:
STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings. Lecture Notes in Computer Science 2996, Springer 2004, ISBN 3-540-21236-1
Invited Lectures
- Claire Kenyon:
Approximation Schemes for Metric Clustering Problems. 1-3 - Erich Grädel:
Positional Determinacy of Infinite Games. 4-18
Structural Complexity (I)
- Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Individual Communication Complexity: Extended Abstract. 19-30 - Bernhard Schwarz:
The Complexity of Satisfiability Problems over Finite Lattices. 31-43 - Kristoffer Arnsfelt Hansen
:
Constant Width Planar Computation Characterizes ACC0. 44-55
Graph Algorithms (I)
- Fedor V. Fomin, Dimitrios M. Thilikos:
A Simple and Fast Approach for Solving Problems on Planar Graphs. 56-67 - Annamária Kovács:
Sum-Multicoloring on Paths. 68-80 - Hannah Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki:
Matching Algorithms Are Fast in Sparse Random Graphs. 81-92
Quantum Computations
- Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien:
Algebraic Results on Quantum Automata. 93-104 - Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita:
Quantum Identification of Boolean Oracles. 105-116
Pattern Inference and Statistics
- Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati:
Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models. 117-128 - Daniel Reidenbach:
A Discontinuity in Pattern Inference. 129-140
Satisfiability - Constraint Satisfaction Problem
- Evgeny Dantsin
, Edward A. Hirsch, Alexander Wolpert:
Algorithms for SAT Based on Search in Hamming Balls. 141-151 - David A. Cohen, Martin C. Cooper
, Peter Jeavons, Andrei A. Krokhin:
Identifying Efficiently Solvable Cases of Max CSP. 152-163 - Elmar Böhler, Edith Hemaspaandra, Steffen Reith, Heribert Vollmer:
The Complexity of Boolean Constraint Isomorphism. 164-175
Scheduling (I)
- Stavros G. Kolliopoulos, George Steiner:
On Minimizing the Total Weighted Tardiness on a Single Machine. 176-186 - Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi
, Jirí Sgall, Tomás Tichý:
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. 187-198 - Tomás Ebenlendr, Jirí Sgall:
Optimal and Online Preemptive Scheduling on Uniformly Related Machines. 199-210
Algorithms
- Christoph Ambühl, Birgitta Weber:
Parallel Prefetching and Caching Is Hard. 211-221 - Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
, Katarzyna E. Paluch
:
Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem. 222-233 - Kedar Dhamdhere, Anupam Gupta, R. Ravi:
Approximation Algorithms for Minimizing Average Distortion. 234-245
Networks (I)
- Pierre Fraigniaud, David Ilcinkas:
Digraphs Exploration with Little Memory. 246-257 - Ioannis Caragiannis, Christos Kaklamanis:
Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks. 258-269 - Thomas Erlebach, Riko Jacob, Matús Mihalák, Marc Nunkesser, Gábor Szabó, Peter Widmayer:
An Algorithmic View on OVSF Code Assignment. 270-281
Automata Theory and Words
- Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin:
The Syntactic Graph of a Sofic Shift. 282-293 - Tero Harju
, Dirk Nowotka:
Periodicity and Unbordered Words: A Proof of Duval?s Conjecture. 294-304 - Daniel Kirsten:
Desert Automata and the Finite Substitution Problem. 305-316
Structural Complexity (II)
- Jan Johannsen:
Satisfiability Problems Complete for Deterministic Logarithmic Space. 317-325 - Till Tantau:
A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number. 326-337 - Régis Barbanchon, Etienne Grandjean:
The Minimal Logically-Defined NP-Complete Problem. 338-349
Path Algorithms
- Torsten Tholey:
Solving the 2-Disjoint Paths Problem in Nearly Linear Time. 350-361 - Torben Hagerup:
Simpler Computation of Single-Source Shortest Paths in Linear Average Time. 362-369
Cryptography
- Mårten Trolin:
Lattices with Many Cycles Are Dense. 370-381 - Ralf Küsters, Thomas Wilke:
Automata-Based Analysis of Recursive Cryptographic Protocols. 382-393
Networks (II)
- Murali K. Ganapathy, Sachin Lodha:
On Minimum Circular Arrangement. 394-405 - Aubin Jarry:
Integral Symmetric 2-Commodity Flows. 406-417 - Christoph Ambühl, Andrea E. F. Clementi, Miriam Di Ianni, Nissan Lev-Tov, Angelo Monti, David Peleg, Gianluca Rossi, Riccardo Silvestri:
Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. 418-427
Logic and Formal Languages
- Thomas Colcombet, Christof Löding:
On the Expressiveness of Deterministic Transducers over Infinite Trees. 428-439 - Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan:
Definability and Regularity in Automatic Structures. 440-451 - Anca Muscholl, Thomas Schwentick, Luc Segoufin:
Active Context-Free Games. 452-464
Graphs Algorithms (II)
- Anna Palbom:
Worst Case Performance of an Approximation Algorithm for Asymmetric TSP. 465-476 - Huaming Zhang, Xin He:
On Visibility Representation of Plane Graphs. 477-488 - Guido Schäfer, Naveen Sivadasan:
Topology Matters: Smoothed Competitiveness of Metrical Task Systems. 489-500
Game Theory and Complexity
- Eduardo Sany Laber:
A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees. 501-512 - Martin Aigner, Gianluca De Marco, Manuela Montangero:
The Plurality Problem with Three Colors. 513-521 - Doron Bustan, Orna Kupferman, Moshe Y. Vardi:
A Measured Collapse of the Modal µ-Calculus Alternation Hierarchy. 522-533
Networks (III)
- Carlos Brito, Eli Gafni, Shailesh Vaya:
An Information Theoretic Lower Bound for Broadcasting in Radio Networks. 534-546 - Thomas Lücking, Marios Mavronicolas
, Burkhard Monien, Manuel Rode:
A New Model for Selfish Routing. 547-558 - Philippe Duchon, Nicolas Hanusse, Nasser Saheb, Akka Zemmari
:
Broadcast in the Rendezvous Model. 559-570
Structural Complexity (III)
- Jin-yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek:
Time-Space Tradeoff in Derandomizing Probabilistic Logspace. 571-583 - Eric Allender, Harry Buhrman, Michal Koucký:
What Can be Efficiently Reduced to the K-Random Strings? 584-595 - Sebastian Bala:
Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms. 596-607
Scheduling (II)
- Vincenzo Auletta, Roberto De Prisco
, Paolo Penna, Giuseppe Persiano:
Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines. 608-619 - Alexander Souza, Angelika Steger:
The Expected Competitive Ratio for Weighted Completion Time Scheduling. 620-631
Algorithmic Information
- Krishna B. Athreya, John M. Hitchcock
, Jack H. Lutz, Elvira Mayordomo:
Effective Strong Dimension in Algorithmic Information and Computational Complexity. 632-643 - Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks:
A Lower Bound on the Competitive Ratio of Truthful Auctions. 644-655
Errata
- Marek Chrobak, Jirí Sgall
:
Errata to Analysis of the Harmonic Algorithm for Three Servers. 656
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.