3-連結グラフに対する点被覆及び連結点被覆問題について

• Item type: SIG Technical Reports(1)
• 公開日: 1995-11-17
• タイトル: 3-連結グラフに対する点被覆及び連結点被覆問題について
• タイトル / 言語: en
• タイトル: On the Complexity of Vertex Cover and Connected Vertex Cover Problems for 3 - Connected Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学工学部第二類（電気系）回路システム工学講座
• 著者所属: 広島大学工学部第二類（電気系）回路システム工学講座
• 著者所属: 広島大学工学部第二類（電気系）回路システム工学講座
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Department of Circuits and Systems, Faculty of Engineering, Hiroshima University
• 著者名: 柴田, 勲男; 藤戸, 敏弘; 渡邉, 敏正
• 著者名(英): Isao, Shibata; Toshihiro, Fujito; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，3?連結グラフに対する点被覆及び連結点被覆問題について考える．但し，3?連結グラフの部分族である準車輪の族及び車輪拡大グラフの族に対象を制限して問題を考える．本稿では，まず車輪拡大グラフに対する点被覆問題がNP完全問題であることを示す．これと既存の結果とを合わせれば，車輪拡大グラフに対する連結点被覆問題もまたNP完全問題であることが示される．次に，準車輪グラフに対する連結点被覆問題を線形マトロイドマッチング問題に帰着させ，線形マトロイドマッチング問題の解法を利用することにより，準車輪グラフに対する最小連結点被覆がO（|V|^)で定められることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 109(1995-AL-048), p. 1-8, 発行日 1995-11-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会