![[-]](/~ygleyzer/course.wiki/images/button-minus.gif)
q2, directed graph matters?
by eial - Monday, 20 July 2009 16:30:59
is the fact that the graph is directed or undirected matters for the answer? the definition in the assignment file is directed graph.
Re: q2, directed graph matters?
by golansha - Monday, 20 July 2009 23:18:31
Then it must be directed.
Re: q2, directed graph matters?
by eial - Tuesday, 21 July 2009 09:06:09
so, when looking on the base definition, the second part of the base definition is means that if there is a edge that that ends in the vertex from V' right?
one more question, when getting the setcover input, do I get the U too?
one more question, when getting the setcover input, do I get the U too?
Re: q2, directed graph matters?
by golansha - Wednesday, 22 July 2009 22:53:43
I didn't understand your first question. The definition is very clear. for every vertex v, v is either in V' or a neighbor of v (u such that (u,v) is in E) is in V'. It does not say anything about edges. There might be an edge that both ends are not in V'. For example if G is the path (a,b,c,d) and V' is {a,d} then the edge (b,c) is not "covered" but its ends are.
A clarification: in the example the path is composed of double edges {(a,b},(b,a),(b,c),(c,b),(c,d),(d,c)}
U is not part of the input, but you can calculate it in polynomial time.
A clarification: in the example the path is composed of double edges {(a,b},(b,a),(b,c),(c,b),(c,d),(d,c)}
U is not part of the input, but you can calculate it in polynomial time.