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

    • Fixed Parameter Complexity and Exact Algorithm

      • Hans Bodlaender et al. (Utrecht University)
    • 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)


  • 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

  • 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