最大共通(接続)部分グラフ問題のための強化分枝限定アルゴリズム【JST・京大機械翻訳】

Zhou Jianrong; He Kun; Zheng Jiongzhi; Li Chu-Min; Liu Yanli

プレプリント

J-GLOBAL ID：202202217828171449 整理番号：22P0275412

最大共通(接続)部分グラフ問題のための強化分枝限定アルゴリズム【JST・京大機械翻訳】

A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2022年01月17日プレプリントサーバーでの情報更新日： 2022年01月17日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

2つの新しいオペレータ,Long-Shortメモリ(LSM)および葉頂点連合Match(LUM)に基づく,最大共通(連結)誘導部分グラフ問題に対する,新しく強化された分岐およびBound(BnB)アルゴリズムを提案した。最大共通(連結)誘起部分グラフを探索する2つのグラフを与えると,LSMの最初の演算子は,最初のグラフの各頂点の短期報酬と2つのグラフの各頂点ペアの長期的報酬を用いて分岐ノードに対するスコアを維持する。この方法で,BnBプロセスは探索木サイズを著しく減らし,アルゴリズム性能を改善する。LUMの第二演算子は,現在の整合頂点に接続した葉頂点を同時にマッチングすることにより性能を改善し,解最適性に影響することなく複数の頂点対を整合させるアルゴリズムを可能にした。2つのオペレータを最先端のBnBアルゴリズムMcSplitに組み込み,McSplit+LLとして得られたアルゴリズムを示した。実験は,McSplit+LLがMcSplit+RLより優れていて,McSplitより優れていて,強化学習を用いたMcSplitのより最近の変種であることを示した。【JST・京大機械翻訳】

, , , , , , , , ,
, , 【Automatic Indexing@JST】

グラフ理論基礎

, , ,

前のページに戻る