课程名称︰高等图论
课程性质︰台大盟校际选课
课程教师︰王有礼
开课学院：
开课系所︰
考试日期（年月日）︰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.