default search action
29. MFCS 2004: Prague, Czech Republic
- Jirí Fiala, Václav Koubek, Jan Kratochvíl:
Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings. Lecture Notes in Computer Science 3153, Springer 2004, ISBN 3-540-22823-3
Invited Lectures
- Jerzy Tiuryn, Ryszard Rudnicki, Damian Wójtowicz:
A Case Study of Genome Evolution: From Continuous to Discrete Time Model. 1-24 - Magnús M. Halldórsson, Guy Kortsarz:
Multicoloring: Problems and Techniques. 25-41 - Rodney G. Downey:
Some Recent Progress in Algorithmic Randomness. 42-83 - Rolf Niedermeier:
Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. 84-103 - Uzi Vishkin:
PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness. 104-105 - Matthew Brand, Sarah F. Frisken Gibson, Neal Lesh, Joe Marks, Daniel Nikovski, Ronald N. Perry, Jonathan S. Yedidia:
Theory and Applied Computing: Observations and Anecdotes. 106-118 - Eduardo Bonelli, Adriana B. Compagnoni, Mariangiola Dezani-Ciancaglini, Pablo Garralda:
Boxed Ambients with Communication Interfaces. 119-148 - Pascal Weil:
Algebraic Recognizability of Languages. 149-175 - Emo Welzl:
Geometric Optimization and Unique Sink Orientations of Cubes p. 176 - Elias Koutsoupias:
Congestion Games and Coordination Mechanisms. 177-179
Graph Algorithms
- Hans L. Bodlaender, Fedor V. Fomin:
Equitable Colorings of Bounded Treewidth Graphs. 180-190 - Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
The Bidimensional Theory of Bounded-Genus Graphs. 191-203 - Hajo Broersma, Fedor V. Fomin, Gerhard J. Woeginger:
Parallel Knock-Out Schemes in Networks. 204-214 - Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou:
Online Algorithms for Disk Graphs. 215-226
Approximations
- Hans-Joachim Böckenhauer, Dirk Bongartz:
Protein Folding in the HP Model on Grid Lattices with Diagonals (Extended Abstract). 227-238 - Hubie Chen, Martin Pál:
Optimization, Games, and Quantified Constraint Satisfaction. 239-250 - André Gronemeier:
Approximating Boolean Functions by OBDDs. 251-262 - Miroslav Chlebík
, Janka Chlebíková
On Approximation Hardness of the Minimum 2SAT-DELETION Problem. 263-273
Graphs and Complexity
- Daniel Král, Pavel Nejedlý:
Group Coloring and List Group Coloring Are Pi2P-Complete (Extended Abstract). 274-286 - Edith Hemaspaandra, Lane A. Hemaspaandra
Complexity Results in Graph Reconstruction. 287-297 - Endre Boros, Khaled M. Elbassioni
Generating Paths and Cuts in Multi-pole (Di)graphs. 298-309 - Zeev Nutov, Raphael Yuster:
Packing Directed Cycles Efficiently. 310-321
Circuits
- Stephen D. Travers:
The Complexity of Membership Problems for Circuits over Sets of Integers. 322-333 - Kristoffer Arnsfelt Hansen, Peter Bro Miltersen:
Some Meet-in-the-Middle Circuit Lower Bounds. 334-345 - Alina Beygelzimer, Mitsunori Ogihara:
The Enumerability of P Collapses P to NC. 346-355 - Alfredo De Santis
On NC1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge. 356-367
General Complexity
- Edith Hemaspaandra, Lane A. Hemaspaandra
All Superlinear Inverse Schemes Are coNP-Hard. 368-379 - Gustav Nordh:
The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups. 380-391 - Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
Generation Problems. 392-403 - Sebastian Bab, Arfst Nickelsen:
One Query Reducibilities Between Partial Information Classes. 404-415
Automata
- Vincent Bernardi, Bruno Durand, Enrico Formenti
A New Dimension Sensitive Property for Cellular Automata. 416-426 - Guillaume Theyssier:
Captive Cellular Automata. 427-438 - Victor Poupet:
Simulating 3D Cellular Automata with 2D Cellular Automata. 439-450 - Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg:
Graph Exploration by a Finite Automaton. 451-462
Parametrized and Kolmogorov Complexity
- Troy Lee, Andrei E. Romashchenko:
On Polynomially Time Bounded Symmetry of Information. 463-475 - John M. Hitchcock
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. 476-487 - Henning Fernau
A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs. 488-499 - Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia:
Polynomial Time Approximation Schemes and Parameterized Complexity. 500-512
Semantics
- Yann Loyer, Umberto Straccia:
Epistemic Foundation of the Well-Founded Semantics over Bilattices. 513-524 - Ruggero Lanotte, Andrea Maggiolo-Schettini, Adriano Peron:
Structural Model Checking for Communicating Hierarchical Machines. 525-536 - Olivier Ly:
Compositional Verification: Decidability Issues Using Graph Substitutions. 537-549 - Rob J. van Glabbeek, Gordon D. Plotkin:
Event Structures for Resolvable Conflict. 550-561
Scheduling
- Leah Epstein, Tamir Tassa:
Optimal Preemptive Scheduling for General Target Functions. 562-573 - Martin Gairing, Thomas Lücking, Marios Mavronicolas
The Price of Anarchy for Polynomial Social Cost. 574-585 - Robert Elsässer, Ulf Lorenz, Thomas Sauerwald:
Agent-Based Information Handling in Large Networks. 586-598 - Nadine Baumann, Ekkehard Köhler:
Approximating Earliest Arrival Flows with Flow-Dependent Transit Times. 599-610
Algebraic Theory of Languages
- Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin:
A Hierarchy of Irreducible Sofic Shifts. 611-622 - Alexei Lisitsa, Igor Potapov:
Membership and Reachability Problems for Row-Monomial Transformations. 623-634 - Libor Polák:
On Pseudovarieties of Semiring Homomorphisms. 635-647 - Zoltán Ésik, Werner Kuich:
An Algebraic Generalization of omega-Regular Languages. 648-659
Games
- Marcel Crâsmaru, Christian Glaßer, Kenneth W. Regan, Samik Sengupta:
A Protocol for Serializing Unique Strategies. 660-672 - Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov:
A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. 673-685 - Hugo Gimbert, Wieslaw Zielonka:
When Can You Play Positionally? 686-697
Languages
- Alexander Okhotin:
The Dual of Concatenation. 698-710 - Klaus Ambos-Spies, Edgar Busse:
Computational Aspects of Disjunctive Sequences. 711-722 - Michael Domaratzki, Kai Salomaa:
Decidability of Trajectory-Based Equations. 723-734
Geometry
- Therese Biedl, Masud Hasan, Alejandro López-Ortiz:
Efficient View Point Selection for Silhouettes of Convex Polyhedra. 735-747 - Therese Biedl, Anna Lubiw, Michael J. Spriggs:
Angles and Lengths in Reconfigurations of Polygons and Polyhedra. 748-759 - Benjamin Doerr, Nils Hebbinghaus, Sören Werth:
Improved Bounds and Schemes for the Declustering Problem. 760-771 - Petr Hlinený:
Crossing Number Is Hard for Cubic Graphs. 772-782
Languages and Complexity
- Victor L. Selivanov, Klaus W. Wagner:
A Reducibility for the Dot-Depth Hierarchy. 783-793 - Klaus Wich:
Sublogarithmic Ambiguity. 794-806 - Elena Petre:
An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx. 807-817 - Lucian Ilie, Pascal Ochem, Jeffrey O. Shallit:
A Generalization of Repetition Threshold. 818-826
Quantum Computing
- Harumichi Nishimura, Tomoyuki Yamakami:
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract). 827-838 - Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra:
Universal Test for Quantum One-Way Permutations. 839-850 - Martin Beaudry, José M. Fernandez, Markus Holzer
A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract). 851-862
XML
- Yves Andre, Anne-Cécile Caron, Denis Debarbieux, Yves Roos
Extraction and Implication of Path Constraints. 863-875 - Béatrice Bouchou, Denio Duarte
Schema Evolution for XML: A Consistency-Preserving Approach. 876-888 - Wim Martens, Frank Neven
Complexity of Decision Problems for Simple Regular Expressions. 889-900
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 18:58 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: