[公告] 博士論文研究計畫口試: 柳青浩 (2014/04/18)

[chinghao]

清華大學資訊工程學系博士研究計劃口試

題 目: Algorithms on Graph Optimization and Unfolding Problems

學 生: 柳青浩

指導教授: 潘雙洪教授

口試委員: 金仲達教授、蔡明哲教授、林春成教授、潘雙洪教授

時 間: 103 年 04 月 18 日 (星期五) 10:00 - 11:00

地 點: 台達館 617 會議室

論文摘要:

In this proposal, we consider both graph optimization problems and
geometrical unfolding problems. For graph optimization problems, we
consider three fundamental and important problems, i.e., computing
maximum independent sets, computing minimum dominating sets and
computing minimum feedback vertex sets, which have many applications
in the real world such as location problems. In detail, we focus on
the independent set (IS) problem, the edge-independent set (EIS)
problem, the dominating set (DS) problem, the independent dominating
set (IDS) problem, the weighted independent dominating set (WIDS)
problem, the minus dominating set (MDS) problem and the feedback
vertex set (FVS) problem. Our methodology is described as follows.
We propose to use decomposition-tree structures of graphs to obtain
polynomial-time algorithms via dynamic programming paradigm. Also,
we plan to obtain NP-completeness results by providing a polynomial-time
reduction from the 3-SAT problem or other NP-complete problems into
the target problem. For problems which are NP-complete on some graph
classes, we propose to provide fixed-parameter tractable (FPT)
algorithms to compute optimal solutions. Moreover, for problems which
are NP-complete on planar graphs, we plan to give polynomial-time
approximation schemes (PTAS) to obtain approximate solutions by using
the well-known baker's method.

Apart from combinatorial graph models, we further consider more
realistic geometric models, that is, one-dimensional tree linkages
lying on two dimensions. In practical aspects, designing unfolding
algorithms for such planar trees has useful applications for moving
robots and folding proteins. We plan to probe partial orders for
disjoint straight chains we select in the planar trees to design
efficient unfolding algorithms. If such an unfolding algorithm cannot
exist, then we would turn to discover locked instances of the planar
trees. To be more precisely, we propose to examine the properties
needed for planar trees to lock, with a focus on finding the smallest
locked trees according to different measures of complexity.

--
▄ ◢ ▄▄▄ ▄▄▄ ▄ ▄▄▄ [1;37m 清大資工 [m
[1;37;44m █ █◣◢█ █▄█ █▄█ █ █▄▄ [33mchinghao [37m 從 [33m p13.cs.nthu.edu.tw [m
█ █◥◤█ █ █ █ █▄▄ █▄▄ [1;37m【楓橋驛站】 telnet://imaple.tw [m