課程名稱 |
圖論演算法 Graph Algorithms |
開課學期 |
101-1 |
授課對象 |
理學院 數學研究所 |
授課教師 |
張鎮華 |
課號 |
MATH7707 |
課程識別碼 |
221 U4070 |
班次 |
|
學分 |
3 |
全/半年 |
半年 |
必/選修 |
選修 |
上課時間 |
星期三1(8:10~9:00)星期五1,2(8:10~10:00) |
上課地點 |
天數101天數101 |
備註 |
總人數上限:50人 |
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1011_Graph_Algorithm |
課程簡介影片 |
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
In this one-semester course, we choose domination theory as the main content. Domination in graph theory has many applications in the real world such as location problems. A dominating set of a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one vertex in D. The domination problem is to determine the domination number gamma(G) of a graph G that is the minimum size of a dominating set of G. Although many theoretic theorems for domination and its variations have been established for a long time, the first algorithmic result on this topic was given by Cockayne, Goodman and Hedetniemi in 1975. They gave a linear-time algorithm for the domination problem in trees by using a labeling method. On the other hand, at about the same time, Garey and John constructed the first (unpublished) proof that the domination problem is NP-complete. Since then, many algorithmic results are studied for variations of the domination problem in different classes of graphs. The content of this course covers the survey of the development on this line during the past 36 years. Polynomial-time algorithms using labeling method, dynamic programming method and primal-dual method are surveyed on trees, interval graphs, strongly chordal graphs, permutation graphs, cocomparability graphs and distance-hereditary graphs. NP-completeness results on domination are also discussed. |
課程目標 |
In this one-semester course, we choose domination theory in graph as an example to demonstrate the theory of graph algorithm. |
課程要求 |
Basic knowledge on graph theory and on algorithm. |
預期每週課後學習時數 |
|
Office Hours |
|
指定閱讀 |
G. J. Chang, Algorithmic aspects of domination in graphs, book chapter. |
參考書目 |
|
評量方式 (僅供參考) |
|
週次 |
日期 |
單元主題 |
第1週 |
9/12,9/14 |
Introduction to domination |
第2週 |
9/19,9/21 |
No classes due to my meeting in Japan |
第3週 |
9/26,9/28 |
Domination in trees |
第4週 |
10/3,10/5 |
Domination in trees (Move to Classroom 101 from this week on) |
第5週 |
10/10,10/12 |
Domination in trees ***** (10/10 holiday) |
第6週 |
10/17,10/19 |
Domination in interval graphs |
第7週 |
10/24,10/26 |
Domination in interval graphs |
第8週 |
10/31,11/2 |
NP-complete results for domination |
第9週 |
11/7,11/9 |
NP-complete results for domination |
第10週 |
11/14,11/16 |
Domination in strongly chordal graphs *** (Midterm Exam, 11/16 Friday) |
第11週 |
11/21,11/23 |
Domination in strongly chordal graphs |
第12週 |
11/28,11/30 |
Domination in distance-hereditary graphs |
第13週 |
12/5,12/7 |
Domination in distance-hereditary graphs |
第14週 |
12/12,12/14 |
Domination in permutation graphs |
第15週 |
12/19,12/21 |
Domination in permutation graphs |
第16週 |
12/26,12/28 |
Domination in cocomparability graphs |
第17週 |
1/2,1/4 |
Domination in cocomparability graphs |
第18週 |
1/9,1/11 |
Final Exam |
|