Let G = (V, E) be an undirected graph. Design algorithms for the following (in each case discuss the complexity of your algorithm): (a) Assume G contains only one cycle. Direct the edges s.t. for each

Let G = (V, E) be an undirected graph. Design algorithms for the following (in each

case discuss the complexity of your algorithm):
(a) Assume G contains only one cycle. Direct the edges s.t. for each u, indegree(u)
$\leq$ 1.
(b) Determine whether it is possible to direct the edges of G s.t. for each u, indegree(u)
$\geq$ 1.
If it is possible, your algorithm should provide a way to do so.
(c) Let S be a subset of edges s.t. every cycle of G has at least one edge in S. Find a
minimum size subset S.

1 Answer

0 Comments

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

0 Comments

Please log in or register to add a comment.

Other Questions