Polynomial reduction

21 problems of Karp :

  • Satisfiability
    • Clique
      • Set packing
      • Vertex cover
        • Set covering
        • Feedback arc set
        • Feedback node set
        • Directed hamiltonian circuit
          • Undirected hamiltonien circuit
  • 0-1 interger programming
  • 3-SAT
    • Chromatic number
      • Clique cover
      • Exact cover
        • Matching 3D
        • Steiner tree
        • Hitting set
        • Knapsack
          • Job sequencing
          • Partition
            • Max-cut

In progress

Publicités