@techreport{oai:ipsj.ixsq.nii.ac.jp:00032312,
 author = {柴田, 勲男 and 藤戸, 敏弘 and 渡邉, 敏正 and Isao, Shibata and Toshihiro, Fujito and Toshimasa, Watanabe},
 issue = {109(1995-AL-048)},
 month = {Nov},
 note = {本論文では，3?連結グラフに対する点被覆及び連結点被覆問題について考える．但し，3?連結グラフの部分族である準車輪の族及び車輪拡大グラフの族に対象を制限して問題を考える．本稿では，まず車輪拡大グラフに対する点被覆問題がNP完全問題であることを示す．これと既存の結果とを合わせれば，車輪拡大グラフに対する連結点被覆問題もまたNP完全問題であることが示される．次に，準車輪グラフに対する連結点被覆問題を線形マトロイドマッチング問題に帰着させ，線形マトロイドマッチング問題の解法を利用することにより，準車輪グラフに対する最小連結点被覆がO（|V|^)で定められることを示す．, The subject of paper is the vertex cover problem (VCP) and the connected vertex cover problem (CVCP) for 3-connected graphs. More specifically, VCP and CVCP for the two classes of 3-connected graphs, called quasi-wheels and super-wheels, are considered. First we prove that VCP for super-wheels is NP-complete. This result, combined with the known result on the relationship between VCP and CVCP for super-wheels, implies that CVCP for super-wheels is NP-complete. By reducing CVCP for quasi-wheels to linear matroid matching problem, it is shown that a minimum connected vertex cover for any given quasi-wheel can be obtained in polynomial time.},
 title = {3-連結グラフに対する点被覆及び連結点被覆問題について},
 year = {1995}
}