2024-03-28T16:55:40Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000319012023-04-27T10:00:04Z01164:02592:02627:02629
反転禁止部分グラフを有する平面グラフ抽出法Heuristic Algorithms for Extracting a Planar Graph with Subgraphs Forbidding their Turning Overjpnhttp://id.nii.ac.jp/1001/00031901/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31901&item_no=1&attribute_id=1&file_no=1Copyright (c) 2003 by the Information Processing Society of Japan広島大学大学院工学研究科日立中国ソフトウェア広島大学大学院工学研究科広島大学大学院工学研究科高藤, 大介姉ヶ山伸一郎木下, 敏行渡邉, 敏正本稿では,反転禁止部分グラフを含むグラフに対する全域平面最大部分グラフ抽出問題を扱う.この問題に対する発見的解法として,PLAN-PWB PLAN-MWW PLAN-DIVIDEが既に提案されている.まず,PLAN-PWBの修正版PLAN-PWB2を提案し,次に,既存解法PLAN-MWWの拡張版PLAN-MWW2,既存解法PLAN-DIVIDEの改良版PLAN-DIVIDE2を提案する.さらに,これらを実装して計算機による既存解法との比較実験を行い,提案手法の性能を実験的に比較評価する.The subject of this paper is the problem of extracting a maximum spanning planar subgraph, which must be embedded asspecified. Heuristic algorithms PLAN-PWB, PLAN-MWW and PLAN-DIVIDE have been proposed so far for this problem. First, we propose PLAN-PWB2 that is an improved version of PLAN-PWB. Then we propose two heuristic algorithms PLAN-MWW2 and PLAN-DIVIDE2: the first one is extended from PLAN-MWW, and the second one is improved from PLAN-DIVIDE by using PLAN-MWW2 instead of PLAN-PWB. Furthermore, experimental results are given to compare performance of these algorithms.AN1009593X情報処理学会研究報告アルゴリズム(AL)200392(2003-AL-091)182003-09-192009-06-30