2024-03-19T12:04:51Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000610162023-04-27T10:00:04Z01164:02592:05623:05624
木幅の上界を求める MCS アルゴリズムについてAn Upper Bound Heuristics for Treewidth Based on MCSjpnhttp://id.nii.ac.jp/1001/00061016/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=61016&item_no=1&attribute_id=1&file_no=1Copyright (c) 2009 by the Information Processing Society of Japan群馬大学大学院工学研究科群馬大学大学院工学研究科平井, 一徹山崎, 浩一木幅とは,グラフパラメータの一つで,グラフが木にどれだけ近いかを表すパラメータである. MCS は, Tarjan 等によって 1970 年代に提案されたアルゴリズムで [SIAM J.Comput., 13 (1984) 566--579] ,木幅の上界を求める上では,比較的高速かつ,良い値を出すことが知られている. Achievable Set は,近年 Lucena によって,木幅を考えるために導入された概念である [Discrete Appl. Math., 155 (2007) 1055--1065] .本研究では, MCS アルゴリズムに Achievable Set の概念を導入することを試みた.そして,提案手法を実装し,実験的に評価を行った.その結果,提案手法は,一般のグラフに対しては効果が見られなかったが,特定のグラフにおいて改善が見られ, MCS が効きにくい一つのグラフ構造を特定することができた.In this paper, we propose and evaluate an algorithm for computing an upper bound on tree-width of graphs. The proposed algorithm is based on combining the well-known “Maximum Cardinality Search” algorithm (MCS for short) due to Tarjan et al. [SIAM J.Comput., 13 (1984) 566--579] ,with the concept “Achievable Set” highlighted by Lucena [Discrete Appl. Math., 155 (2007) 1055--1065] . The effectiveness of our algorithm was not experimentally confirmed for general graphs. Our experimental results, however, show that the algorithm works well for some specific graphs.AN1009593X研究報告アルゴリズム(AL)20099(2009-AL-122)59662009-01-232009-08-18