NP-Completeness: Theory and Applications

Editor: Teofilo F. Gonzalez
(teo@cs.ucsb.edu)

Prospectus Web Page

  • Table of Contents

  • Theory

    • Introduction / Notation / Overview

      T. F. Gonzalez (University of California, Santa Barbara)


    • Historical Perspective and Recent Advances

    • Reducibility and Cook's Theorem

    • Basic Reductions

    • Typical Reductions

    • Strong NP-Completeness

    • NP-hard problems

    • Planar and 2D Reductions

    • Efficient Transformations

    • Approximation Classes

    • Inapproximability


      • M. Szegedy (Rutgers University)


    • Average Case Completeness

      • R. Venkatesan (Microsoft Research)


    • Related Complexity Classes

    • Propositional Proof Complexity

      • Nicola Galesi (Universitat Politèica de Catalunya) and Edward Hirsch (Steklov Mathematical Institute)


    • Exact and Fixed Parameter Algorithms

      • Hans Bodlaender (Utrecht University), Rodney G. Downey (Victoria University of Wellington) and Dimitrios M. Thilikos (National and Kapodistrian University of Athens)
    • Open Problems

  • Applications

  • Packing

  • Routing (TSP, Vehicle, etc)

  • Trees (Steiner, spanning, etc.)

  • Scheduling


    • NP-hardness of some scheduling problems
    J.Y.T. Leung (New Jersey Inst. of Tech.)


    Title Pending

    Vadim Timkovsky (U. of Sydney)


    Complexity results for scheduling problems

    Peter Brucker and Sigrid Knust (Universität Osnabrück)


  • Graph Problems
  • Selecting

  • Partitioning


    • Chromatic Numbers: The Typical Case

    Josep Diaz (Universitat Politecnica de Catalunya), Lefteris Kirousis (University of Patras), and Dieter Mitsche (ETH Zentrum)


  • Arrangements

  • Embedding

  • Miscellaneous


    • Transitive Reductions for Networks

    Kedsuda Apichonbancha (U. Illinois at Chicago), Piotr Berman (Penn. State U.), Bhaskar DasGupta (U. Illinois at Chicago), and Samir Khuller (U. of Maryland)


  • SAT

    • Practical SAT Solving

    Marijn Heule (TU Delft), Armin Biere (Johannes Kepler University) and Joao Marques Silva (University of Southampton)


  • Flow Problems


    • Selfish splittable flows and NP-completeness

    A. C. Kaporis and P. Spirakis (U. of Patras and CTI)


  • Bioinformatics

  • Superstring and Supersequence Problems


    • Title Pending


    Vadim Timkovsky (U. of Sydney)


  • Message Routing (computer, optical, wireless and sensor)

  • VLSI \& Rectilinear Steiner Trees

  • Image Processing

  • Logic

  • Computational Geometry

  • Code Generation and Register Allocation

  • Protocols and Security

  • Data Bases, Query Languages, and Mining

  • Internet

  • Games and Puzzles


    • Complexity of Combinatorial Games


    A. Fraenkel (Weizmann Institute of Science), E. Demaine (MIT), and Bob Hearne (Dartmouth)


  • Miscellaneous