課程名稱︰高等圖論
課程性質︰臺大盟校際選課
課程教師︰王有禮
開課學院：
開課系所︰
考試日期（年月日）︰2015/04/29
考試時限（分鐘）：180
試題 :
1. (20%) Prove that the dominating set decision problem is NP-complete.
2. (20%) Find the closed form of the following recurrence formula:
0 if n = 0,
1 if n = 1,
t = 2 if n = 2,
n 5t - 8t + 4t if n >= 3.
n-1 n-2 n-3
3. (20%) Show that, by using the search tree technique, the maximal
n
independent set problem can be solved in O*(1.3803 ) time,
where n is the number of vertices in graph G.
n
4. (20%) Show that there exists an O*(1.4422 )-time algorithm to
to determine whether X(G) <= 3 gor a graph G of n vertices,
where X(G) denotes the chromatic number of G.
n
5. (20%) Show that there exists an O*(3 )-time algorithm to solve
the domatic partition problem for a graph G of n vertices.