Exercise 5 - Week 17/11/2024

    Question 5 - Choose the correct alternative:

a) TSP (Travelling-Salesperson-Problem) can be reduced to finding an Eulerian Cycle for any graph.

b) The min-edge-cover problem can be solved with polynomial-time flow algorithm for bipartite graphs.

c) The Maximum-Flow-Problem is prooven to be a NP problem, this means that there isn't an algorithm that solves the problem in polynomial time.

d) The Travelling-Salesperson-Problem (TSP) is prooven to be a P problem, this means that there is an algorithm that solves the problem in polynomial time.

e) None of the above


Original idea by: Daniel Hosomi

Comments

Post a Comment

Popular posts from this blog

Exercise 1 - Week 11/08/2024

  Question 1 - Consider the DFS algorithm, choose the wrong alternative: a) The algorithm can be implemented using a data structure similar to a Stack. b) The DFS is a base algorithm to others like Tarjan's Algorithm (to find bridges and articulation points). c) The DFS follows the LIFO order (the last node visited in the DFS is the first to be fully processed). d) The DFS algorithm finds the shortest path between its origin vertex and every other node in the graph (considering that the graph is not pondered). e) None of the above Original idea by: Daniel Hosomi
Read more

Exercise 3 - Week 08/09/2024

  Question 3 - Consider the the Scale-Free property and its context, choose the wrong alternative: a) The WWW is an example of a Scale-Free graph. b) Random Networks usually have a scale of node degree (an average degree among all nodes that is similar to the degree of every node on the network). c) Scale-Free graphs node usually have different degrees and the ones with the higher degrees are called HUB's.  d) None real network is a Scale-Free graph. e) None of the above Original idea by: Daniel Hosomi
Read more