2024-03-28T21:19:47Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001904862022-10-21T05:24:51Z00581:09322:09329
最大辺重みクリーク問題に対する局所探索法のためのデータ構造Data Structures for Local Search Algorithms for the Maximum Edge-weight Clique Problemjpn[一般論文] 最大辺重みクリーク問題,NP困難,局所探索法,データ構造http://id.nii.ac.jp/1001/00190398/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=190486&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of Japan神戸大学大学院工学研究科神戸大学大学院工学研究科神戸大学大学院工学研究科神戸大学大学院工学研究科清水, 悟司石原, 諒大山口, 一章増田, 澄男辺に重みが付与された無向グラフが与えられたとき,重みの和が最大となるクリークを求める問題を最大辺重みクリーク問題という.本稿ではこの問題に対する局所探索法において近傍を管理するためのデータ構造を2つ提案する.計算機実験により2つの局所探索法でデータ構造を比較し,提案法は従来法より性能が良いことを確認した.また,グラフの性質や計算機のメモリに応じて提案するデータ構造を使い分けることで,効率良く探索を行えることを確認した.The maximum edge-weight clique problem is to find the clique of maximum weight for a given edge-weighted undirected graph. In this paper, we propose two data structures to manage neighborhood in local search algorithms. By some computational experiments, we compared our proposal data structures with two local search algorithms and confirmed ours work better than a previous one. By applying proposal data structures properly, we confirmed local search algorithms work efficiently.AN00116647情報処理学会論文誌597141514242018-07-151882-77642018-07-12