臺灣博碩士論文加值系統

本篇論文的主要內容是在討論有向圖上的回饋點集問題. 對沒有點的入度
數或出度數超過２的有向圖和沒有入度數或出度數超過３的平面有向圖而
言, 回饋點集問題已經被證明是NP-complete.在這篇論文裡, 我們將證
明: 對入度數加出度數的總和不超過３的有向圖和沒有入度數或出度數超
過２的平面有向圖( 或雙分平面有向圖 )而言, 回饋點集問題也是NP-
complete.我們也將證明: 對沒有點的入度數加出度數的總和超過２的有
向圖和沒有點的入度數加出度數總和超過３的平面有向圖而言, 回饋點集
問題是存在多項式時間的演算法的.

This paper deals with the feedback vertex set ( FVS ) problem
for various digraphs. It was proved that the FVS problem is NP-
complete for general digraphs and remains NP-complete for
digraphs having no in-degree or out-degree exceeding 2, and for
planar digraphs having no in-degree or out-degree exceeding 3.
In this paper, we shall show that the FVS problem remains NP-
complete even for digrpahs in which no vertex has total in-
degree and out-degree more than 3, for planar (or planar
bipartite) digraphs having no in-degree or out-degree exceeding
2. Moreover, we shall also show that the FVS problem is
solvable in polynomial time for digraphs in which no vertex has
total in-degree and out-degree more than 2, and for planar
digraphs in which no vertex total has total in-degree and out-
degree more than 3.