That clause postmodifier

Classified in Computers

Written at on English with a size of 2.46 KB.

  • SAT p Ind. Set. - 2
  • Ind.Set p Vertex Cover - 1
  • Vertex Cover p Set Cover
  • Vertex Cover p Hitting Set
  • SAT p 3-COL
  • SAT p Ham. Cycle
  • Ham. Cyc. p  Ham. Path
  • Ham. Cyc. p  TSP
  • Hamiltonian Path With Specified Extremes - 3
  • Independent Set to Diverse Subset - 4

1- input: graph G, integer k
    .call the black-box for Vertex Cover with input G,
    .N − k where n is the number of nodes of G 3:
    .Return the result (’yes’ or ’no’) of the previous call

2- input: CNF F
.Construct a graph G where the nodes of G are the literals occurring in F (with possible repetitions) and the following edges:
- An edge joining every pair of complementary literals
- An edge joining literals occurring in the same clause.
.Call the black-box for Independent Set with input G, k where k is the number of clauses of F
.Return the result (’yes’ or ’no’) of the previous call

3- input: a graph G and two nodes x and y
.Construct, using G, a new graph H in the following way: Initially, place in H all nodes and edges in G. Furthermore, we add to H two new nodes, that we call x' and y' , and the following new edges: (x', x) and (y', y).
.Call the black-box for Hamiltonian Problem with input H
.Return the result (yes or no) of the previous call

4- input: a graph G and a non-negative integer k
.Construct a matrix A in the following way: Matrix A has one row for each node in G and one column for each edge in G. So, we can think that the customers of A correspond to nodes of G and the products of A correspond to edges of G. Finally, every entry of matrix A is assigned to a 0 or 1 in the following way. Let v be a node in G and e be an edge in G, then the entry Av,e is 1 if node v is incident to edge e and 0 otherwise.
.Call the black box for the Diverse Subset Problem with input (A, k)
.Return the result (yes or no) of the previous call

Entradas relacionadas: