7. (15%) Design a polynomial-time algorithm for the following problem.
Input: An n-node undirected graph G.
Output:
"'Yes', if there is a cycle of length at most n/2 (i.e., a cycle that has at most n/2 nodes) in G;
"No", otherwise.
***Please give the high-level idea of your algorithm and explain why it has polynomial running time. ***
阿摩線上測驗
登入