Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2003

Fundamentals of Computation Theory

14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings

Editors:

  1. Andrzej Lingas

    1. Department of Computer Science, Lund University, Lund, Sweden

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Bengt J. Nilsson

    1. School of Technology and Society, Malmö University, Malmö, Sweden

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2751)

Conference series link(s): FCT: International Symposium on Fundamentals of Computation Theory

Conference proceedings info: FCT 2003.

Sections

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (39 papers)

  1. Front Matter

    PDF

  2. Approximability 1

    3. Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques

      • Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich
      Pages 15-26

  3. Approximability 2

    1. Inapproximability Results for Bounded Variants of Optimization Problems

      • Miroslav Chlebík, Janka Chlebíková
      Pages 27-38

    2. Approximating the Pareto Curve with Local Search for the Bicriteria TSP(1,2) Problem

      • Eric Angel, Evripidis Bampis, Laurent Gourvès
      Pages 39-48

  4. Algorithms 1

    1. Linear Time Algorithms for Some NP-Complete Problems on (P 5,Gem)-Free Graphs

      • Hans Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy Spinrad
      Pages 61-72

    2. Graph Searching, Elimination Trees, and a Generalization of Bandwidth

      • Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle
      Pages 73-85

    4. Composing Equipotent Teams

      • Mark Cieliebak, Stephan Eidenbenz, Aris Pagourtzis
      Pages 98-108

  5. Algorithms 2

    1. Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers

      • Ivan Bjerre Damgård, Gudmund Skovbjerg Frandsen
      Pages 109-117

    2. An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates

      • Ivan Bjerre Damgård, Gudmund Skovbjerg Frandsen
      Pages 118-131

    4. Fast Periodic Correction Networks

      • Grzegorz Stachowiak
      Pages 144-156

  6. Networks and Complexity

    1. Games and Networks

      • Christos Papadimitriou
      Pages 157-157

    2. One-Way Communication Complexity of Symmetric Boolean Functions

      • Jan Arpe, Andreas Jakoby, Maciej Liśkiewicz
      Pages 158-170

    3. Circuits on Cylinders

      • Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay
      Pages 171-182

  7. Computational Biology

    1. Fast Perfect Phylogeny Haplotype Inference

      • Peter Damaschke
      Pages 183-194

    2. On Exact and Approximation Algorithms for Distinguishing Substring Selection

      • Jens Gramm, Jiong Guo, Rolf Niedermeier
      Pages 195-209
Back to top

Other Volumes

  1. Fundamentals of Computation Theory

Back to top

Keywords

Back to top

Editors and Affiliations

  • Department of Computer Science, Lund University, Lund, Sweden

    Andrzej Lingas

  • School of Technology and Society, Malmö University, Malmö, Sweden

    Bengt J. Nilsson

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation