文献

J-GLOBAL ID：202002265244424710   整理番号：20A1807989

正則グラフの平均頂点間距離最小化のための遺伝アルゴリズム

A Genetic Algorithm for Minimizing Average Shortest Path Length of Regular Graphs

著者 (3件)： 林嶺司 (岡山大 大学院自然科学研究科) ,  右田剛史 (岡山大 大学院自然科学研究科) ,  高橋規一 (岡山大 大学院自然科学研究科)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 120  号： 26(NLP2020 1-10)  ページ： 11-16 (WEB ONLY)  発行年： 2020年05月08日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 与えられた頂点数と次数をもつ正則グラフの中で平均頂点間距離を最小にするものを求める問題に対し,遺伝アルゴリズムを用いた新たな近似解法を提案する.この問題は探索対象が正則グラフに限定されているため,既存の遺伝アルゴリズムを直接適用することはできない.そこで本報告では,グラフの正則性を保証する交叉や突然変異の方法を提案する.また,提案する近似解法の有効性を実験的に評価する.(著者抄録)

シソーラス用語： *グラフ理論 ,  *正則化 ,  *頂点 ,  *遺伝的アルゴリズム ,  近似法 ,  数学的性質 ,  交差 ,  突然変異
準シソーラス用語： 近似解法 ,  *正則グラフ ,  正則性

分類 (2件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z)

引用文献 (13件)：

• V. G. Cerf, D. D. Cowan, R. C. Mullin and R. G. Stanton, “Computer networks and generalized Moore graphs,” Congressus Numerantium, vol.9, pp.379-398, 1973.
• V. G. Cerf, D. D. Cowan, R. C. Mullin and R. G. Stanton, “A lower bound on the average shortest path length in regular graphs,” Networks, vol.4, no.4, pp.335-342, 1974.
• A. J. Hoffman and R. R. Singleton, “On Moore graphs with diameters 2 and 3,” IBM Journal of Research and Development, vol.4, pp.497-504, 1960.
• E. Bannai and T. Ito, “Regular graphs with excess one,” Discrete Mathematics, vol.37, pp.147-158, 1981.
• 里谷 佳紀, 高橋 規一, “一般化ムーアグラフの効率的探索法の提案と評価,” 電子情報通信学会技術研究報告, vol.118, no.75, pp.85-90, 2018.

タイトルに関連する用語 (5件)： 正則グラフ ,  平均 ,  頂点 ,  最小化 ,  遺伝アルゴリズム