NP optimization problems (definition)
-
22-04-2021 - |
题
I'm trying to understand the definition of NPO.
I read the definition here : http://www.nada.kth.se/~viggo/wwwcompendium/node2.html
If we consider trying to find a minimal vertice cover, what is I,sol(x) and m ? (goal is min)
解决方案
Judging by the link you posted I think this is the interpretation for minimal vertex cover:
- I: The set of all graphs.
- sol(x): The set of possible solutions to a graph x ∈ I, that is all subsets of vertices that cover all edges.
- m(x,y): The value of solution y to instance x. In the vertex cover case the number of vertices in the set.
不隶属于 StackOverflow