課程資訊
課程名稱
圖論演算法
Graph Algorithms 
開課學期
101-1 
授課對象
理學院  數學研究所  
授課教師
張鎮華 
課號
MATH7707 
課程識別碼
221 U4070 
班次
 
學分
全/半年
半年 
必/選修
選修 
上課時間
星期三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