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
Algorithms for SAT Based on Search in Hamming Balls. 141-151 - David A. Cohen, Martin C. Cooper
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
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
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
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
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
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
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
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.
last updated on 2024-12-13 19:00 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: