Mathematical Foundations of Computer Science 2004

1. Front Matter

   PDF

2. Invited Lectures

   1. A Case Study of Genome Evolution: From Continuous to Discrete Time Model

      • Jerzy Tiuryn, Ryszard Rudnicki, Damian Wójtowicz

      Pages 1-24

   2. Multicoloring: Problems and Techniques

      • Magnús M. Halldórsson, Guy Kortsarz

      Pages 25-41

   3. Some Recent Progress in Algorithmic Randomness

      • Rod Downey

      Pages 42-83

   4. Ubiquitous Parameterization — Invitation to Fixed-Parameter Algorithms

      • Rolf Niedermeier

      Pages 84-103

   5. PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness

      • Uzi Vishkin

      Pages 104-105

   6. Theory and Applied Computing: Observations and Anecdotes

      • Matthew Brand, Sarah Frisken, Neal Lesh, Joe Marks, Daniel Nikovski, Ron Perry et al.

      Pages 106-118

   7. Boxed Ambients with Communication Interfaces

      • Eduardo Bonelli, Adriana Compagnoni, Mariangiola Dezani-Ciancaglini, Pablo Garralda

      Pages 119-148

   8. Algebraic Recognizability of Languages

      • Pascal Weil

      Pages 149-175

   9. Geometric Optimization and Unique Sink Orientations of Cubes

      • Emo Welzl

      Pages 176-176

   10. Congestion Games and Coordination Mechanisms

       • Elias Koutsoupias

       Pages 177-179

3. Graph Algorithms

   1. Equitable Colorings of Bounded Treewidth Graphs

      • Hans L. Bodlaender, Fedor V. Fomin

      Pages 180-190

   2. The Bidimensional Theory of Bounded-Genus Graphs

      • Erik D. Demaine, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos

      Pages 191-203

   3. Parallel Knock-Out Schemes in Networks

      • Hajo Broersma, Fedor V. Fomin, Gerhard J. Woeginger

      Pages 204-214

   4. Online Algorithms for Disk Graphs

      • Ioannis Caragiannis, Aleksei Fishkin, Christos Kaklamanis, Evi Papaioannou

      Pages 215-226

4. Approximations

   1. Protein Folding in the HP Model on Grid Lattices with Diagonals

      • Hans-Joachim Böckenhauer, Dirk Bongartz

      Pages 227-238

   2. Optimization, Games, and Quantified Constraint Satisfaction

      • Hubie Chen, Martin Pál

      Pages 239-250

   3. Approximating Boolean Functions by OBDDs

      • Andre Gronemeier

      Pages 251-262

   4. On Approximation Hardness of the Minimum 2SAT-DELETION Problem

      • Miroslav Chlebík, Janka Chlebíková

      Pages 263-273

5. Graphs and Complexity

   1. Group Coloring and List Group Coloring Are Π₂ ^P-Complete

      • Daniel Král’, Pavel Nejedlý

      Pages 274-286

This volume contains the papers presented at the 29th Symposium on Mat- matical Foundations of Computer Science, MFCS 2004, held in Prague, Czech Republic, August 22–27, 2004. The conference was organized by the Institute for Theoretical Computer Science (ITI) and the Department of Theoretical Com- terScienceandMathematicalLogic(KTIML)oftheFacultyofMathematicsand Physics of Charles University in Prague. It was supported in part by the Eu- pean Association for Theoretical Computer Science (EATCS) and the European Research Consortium for Informatics and Mathematics (ERCIM). Traditionally, the MFCS symposia encourage high-quality research in all branches of theoretical computer science. Ranging in scope from automata, f- mal languages, data structures, algorithms and computational geometry to c- plexitytheory,modelsofcomputation,andapplicationsincludingcomputational biology, cryptography, security and arti?cial intelligence, the conference o?ers a unique opportunity to researchers from diverse areas to meet and present their results to a general audience. The scienti?c program of this year’s MFCS took place in the lecture halls of the recently reconstructed building of the Faculty of Mathematics and P- sics in the historical center of Prague, with the famous Prague Castle and other celebratedhistoricalmonumentsinsight.Theviewfromthewindowswasach- lengingcompetitionforthespeakersinthe?ghtfortheattentionoftheaudience. But we did not fear the result: Due to the unusually tough competition for this year’s MFCS, the admitted presentations certainly attracted considerable in- rest. The conference program (and the proceedings) consisted of 60 contributed papers selected by the Program Committee from a total of 167 submissions.

• Automat
• XML
• algorithms
• automata
• complexity
• computer
• computer science
• algorithm analysis and problem complexity
• data structures

• Institute for Theoretical Computer Science and Department of Applied Mathematics, Charles University, Prague, Czech Republic

  Jiří Fiala, Jan Kratochvíl

• Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University, Praha1, Czech Republic

  Václav Koubek

Policies and ethics