14. FCT 2003: Malmö, Sweden

@proceedings{DBLP:conf/fct/2003,
  editor    = {Andrzej Lingas and
               Bengt J. Nilsson},
  title     = {Fundamentals of Computation Theory, 14th International Symposium,
               FCT 2003, Malm{\"o}, Sweden, August 12-15, 2003, Proceedings},
  booktitle = {FCT},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2751},
  year      = {2003},
  isbn      = {3-540-40543-7},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Approximability 1

• Sanjeev Arora:
  Proving Integrality Gaps without Knowing the Linear Program. 1
  Electronic Edition (link) BibTeX
• Takao Asano:
  An Improved Analysis of Goemans and Williamson's LP-Relaxation for MAX SAT. 2-14
  Electronic Edition (link) BibTeX
• Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich:
  Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques. 15-26
  Electronic Edition (link) BibTeX

Approximability 2

• Miroslav Chlebík, Janka Chlebíková:
  Inapproximability Results for Bounded Variants of Optimization Problems. 27-38
  Electronic Edition (link) BibTeX
• Eric Angel, Evripidis Bampis, Laurent Gourvès:
  Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem. 39-48
  Electronic Edition (link) BibTeX
• Monaldo Mastrolilli:
  Scheduling to Minimize Max Flow Time: Offline and Online Algorithms. 49-60
  Electronic Edition (link) BibTeX

Algorithms 1

• Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy Spinrad:
  Linear Time Algorithms for Some NP-Complete Problems on (P₅, Gem)-Free Graphs. 61-72
  Electronic Edition (link) BibTeX
• Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle:
  Graph Searching, Elimination Trees, and a Generalization of Bandwidth. 73-85
  Electronic Edition (link) BibTeX
• Joachim Gudmundsson:
  Constructing Sparse t-Spanners with Small Separators. 86-97
  Electronic Edition (link) BibTeX
• Mark Cieliebak, Stephan Eidenbenz, Aris Pagourtzis:
  Composing Equipotent Teams. 98-108
  Electronic Edition (link) BibTeX

Algorithms 2

• Ivan Damgård, Gudmund Skovbjerg Frandsen:
  Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers. 109-117
  Electronic Edition (link) BibTeX
• Ivan Damgård, Gudmund Skovbjerg Frandsen:
  An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. 118-131
  Electronic Edition (link) BibTeX
• Marcin Kik:
  Periodic Multisorting Comparator Networks. 132-143
  Electronic Edition (link) BibTeX
• Grzegorz Stachowiak:
  Fast Periodic Correction Networks. 144-156
  Electronic Edition (link) BibTeX

Networks and Complexity

• Christos H. Papadimitriou:
  Games and Networks. 157
  Electronic Edition (link) BibTeX
• Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
  One-Way Communication Complexity of Symmetric Boolean Functions. 158-170
  Electronic Edition (link) BibTeX
• Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay:
  Circuits on Cylinders. 171-182
  Electronic Edition (link) BibTeX

Computational Biology

• Peter Damaschke:
  Fast Perfect Phylogeny Haplotype Inference. 183-194
  Electronic Edition (link) BibTeX
• Jens Gramm, Jiong Guo, Rolf Niedermeier:
  On Exact and Approximation Algorithms for Distinguishing Substring Selection. 195-209
  Electronic Edition (link) BibTeX
• Patricia A. Evans, Andrew D. Smith:
  Complexity of Approximating Closest Substring Problems. 210-221
  Electronic Edition (link) BibTeX

Computational Geometry

• Binhai Zhu:
  On Lawson's Oriented Walk in Random Delaunay Triangulations. 222-233
  Electronic Edition (link) BibTeX
• Mikael Hammar, Bengt J. Nilsson, Mia Persson:
  Competitive Exploration of Rectilinear Polygons. 234-245
  Electronic Edition (link) BibTeX
• Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack:
  An Improved Approximation Algorithm for Computing Geometric Shortest Paths. 246-257
  Electronic Edition (link) BibTeX
• Zheng Sun, John H. Reif:
  Adaptive and Compact Discretization for Weighted Region Optimal Path Finding. 258-270
  Electronic Edition (link) BibTeX
• John H. Reif, Zheng Sun:
  On Boundaries of Highly Visible Spaces and Applications. 271-283
  Electronic Edition (link) BibTeX

Computational Models and Complexity

• Gheorghe Paun:
  Membrane Computing. 284-295
  Electronic Edition (link) BibTeX
• Farid M. Ablayev, Aida Gainutdinova:
  Classical Simulation Complexity of Quantum Machines. 296-302
  Electronic Edition (link) BibTeX
• Luis Antunes, Lance Fortnow, N. V. Vinodchandran:
  Using Depth to Capture Average-Case Complexity. 303-310
  Electronic Edition (link) BibTeX

Structural Complexity

• Richard J. Lipton, Anastasios Viglas:
  Non-uniform Depth of Polynomial Time and Space Simulations. 311-320
  Electronic Edition (link) BibTeX
• Martin Kutrib:
  Dimension- and Time-Hierarchies for Small Time Bounds. 321-332
  Electronic Edition (link) BibTeX
• Philippe Moser:
  Baire's Categories on Small Complexity Classes. 333-342
  Electronic Edition (link) BibTeX

Formal Languages

• Jean Berstel, Luc Boasson, Olivier Carton, Bruno Petazzoni, Jean-Eric Pin:
  Operations Preserving Recognizable Languages. 343-354
  Electronic Edition (link) BibTeX
• Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux:
  Languages Defined by Generalized Equality Sets. 355-363
  Electronic Edition (link) BibTeX
• Michele Bugliesi, Ambra Ceccato, Sabina Rossi:
  Context-Sensitive Equivalences for Non-interference Based Protocol Analysis. 364-375
  Electronic Edition (link) BibTeX
• Werner Kuich, Klaus W. Wagner:
  On the Exponentiation of Languages. 376-386
  Electronic Edition (link) BibTeX
• Christian Pech:
  Kleene's Theorem for Weighted Tree-Automata. 387-399
  Electronic Edition (link) BibTeX

Logic

• Till Tantau:
  Weak Cardinality Theorems for First-Order Logic. 400-411
  Electronic Edition (link) BibTeX
• Wan Fokkink, Rob J. van Glabbeek, Paulien de Wind:
  Compositionality of Hennessy-Milner Logic through Structural Operational Semantics. 412-422
  Electronic Edition (link) BibTeX
• Andrzej Szalas:
  On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems. 423-431
  Electronic Edition (link) BibTeX