鑽石圖上回饋問題之研究

On the Study of Feedback Problems on Diamond Graphs

陳彥良(Y. L. Chen)

指導教授 ： 李家同

國立暨南國際大學/管理學院/資訊管理學系/碩士(2006年)

摘要

論文摘要 這裡有二個回饋問題. 一個是權重在點上的回饋問題(簡稱：WFVP)，另一個則是權重在邊上的回饋問題(簡稱：WFEP)。WFVP是要找出點的子集合並且權重最小，而且原圖拿掉這個子集合後，原圖會變成沒有迴圈；而WFEP則是要找出邊的子集合並且權重最小，而且原圖拿掉這個子集合後，原圖同樣地會變成沒有迴圈。 這二個問題，在一般圖形上已經被證明是 NP-hard 的問題。所以在這個論文中，我們第一個要介紹的是二種變形的鑽石圖，一種是將二個鑽石圖並聯，一種是將二個鑽石圖串聯。我們也提出一個簡單的演算法在這二種圖形上解決WFVP的問題。最後，我們將介紹權重在邊上的鑽石圖，並且提出一個演算法來解決WFEP的問題，在這種鑽石圖上。

關鍵字

回饋點問題 ； 回饋邊問題 ； 鑽石圖形 ； 並聯和串聯鑽石圖形

並列摘要

Abstract
There are two kinds of feedback problems. One is the weighted feedback vertex problem (WFVP) and the other is weighted feedback edge problem (WFEP). The WFVP (respectively WFEP) problem is to find a subset of vertices (respectively edges) with minimum total weight that intersects every undirected cycle in a given graph. These two problems on general graphs are known to be NP-hard. In this thesis, first we introduce two variations of diamond graphs. One is the parallel connection of two diamonds and the other is the serial connection of two diamonds. We shall propose a simple algorithm to solve the minimum weighted feedback vertex problem in the two kinds of diamonds. Finally, we introduce a diamond with weighted edges and we shall propose a simple algorithm to solve the minimum weighted feedback edge problem in this diamond.

並列關鍵字

Weighted Feedback Vertex Problem ； Weighted Feedback Edge Problem ； Diamond Graph ； Parallel and Serial Diamond Graph.

參考文獻

Bibliography

[BBF1995] Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs, V. Bafna, P. Berman, T. Fujito, in: ISAAC95, Algorithms and Computation, in: Lecture Notes in Comput. Sci., vol. 1004, Springer-Verlag, Berlin, 1995, pp. 142–151.

[BG1994] Approximation algorithms for the loop cutset problem, A. Becker, D. Geiger, in: Proc. 10th Conf. on Uncertainty in Artificial Intelligence, 1994, pp. 60–68.

[CL1997] Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs, M.S. Chang, Y.D. Liang, Acta Inform. 34 (1997) 337–346.

[CCGP2005] A linear-time algorithm for the weighted feedback vertex problem on diamonds, F. Carrabs, R. Cerulli, M. Gentili, G. Parlatob, Inform. Process. Lett. 94 (2005) 29–35.