14. FCT 2003: Malmö, Sweden
- Andrzej Lingas, Bengt J. Nilsson:
Fundamentals of Computation Theory, 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings. Lecture Notes in Computer Science 2751, Springer 2003, ISBN 3-540-40543-7
Approximability 1
- Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich:
Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques. 15-26
Approximability 2
- Miroslav Chlebík, Janka Chlebíková:
Inapproximability Results for Bounded Variants of Optimization Problems. 27-38 - Eric Angel, Evripidis Bampis, Laurent Gourvès:
Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem. 39-48
Algorithms 1
- Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy P. Spinrad:
Linear Time Algorithms for Some NP-Complete Problems on (P5, Gem)-Free Graphs. 61-72 - Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle:
Graph Searching, Elimination Trees, and a Generalization of Bandwidth. 73-85
Algorithms 2
- Ivan Damgård, Gudmund Skovbjerg Frandsen:
Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers. 109-117 - Ivan Damgård, Gudmund Skovbjerg Frandsen:
An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. 118-131
Networks and Complexity
- Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
One-Way Communication Complexity of Symmetric Boolean Functions. 158-170
Computational Biology
- Jens Gramm, Jiong Guo, Rolf Niedermeier:
On Exact and Approximation Algorithms for Distinguishing Substring Selection. 195-209
Computational Geometry
- Mikael Hammar, Bengt J. Nilsson, Mia Persson:
Competitive Exploration of Rectilinear Polygons. 234-245 - Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack:
An Improved Approximation Algorithm for Computing Geometric Shortest Paths. 246-257 - Zheng Sun, John H. Reif:
Adaptive and Compact Discretization for Weighted Region Optimal Path Finding. 258-270
Computational Models and Complexity
- Luis Antunes, Lance Fortnow, N. V. Vinodchandran:
Using Depth to Capture Average-Case Complexity. 303-310
Structural Complexity
- Richard J. Lipton, Anastasios Viglas:
Non-uniform Depth of Polynomial Time and Space Simulations. 311-320
Formal Languages
- Jean Berstel, Luc Boasson, Olivier Carton, Bruno Petazzoni, Jean-Eric Pin:
Operations Preserving Recognizable Languages. 343-354 - Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux:
Languages Defined by Generalized Equality Sets. 355-363 - Michele Bugliesi, Ambra Ceccato, Sabina Rossi:
Context-Sensitive Equivalences for Non-interference Based Protocol Analysis. 364-375
Logic
- Wan Fokkink, Rob J. van Glabbeek, Paulien de Wind:
Compositionality of Hennessy-Milner Logic through Structural Operational Semantics. 412-422 - Andrzej Szalas:
On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems. 423-431