文献

J-GLOBAL ID：200902215525013900   整理番号：09A1005705

条件的遺伝的操作を行う遺伝的アルゴリズムを用いた2部部分グラフ問題の求解

Solving the Bipartite Subgraph Problem Using Genetic Algorithm with Conditional Genetic Operators

著者 (3件)： CHEN Zhi-Qiang (Univ. Fukui, Fukui-shi, JPN) ,  WANG Rong-Long (Univ. Fukui, Fukui-shi, JPN) ,  OKAZAKI Kozo (Univ. Fukui, Fukui-shi, JPN)
資料名： IEEJ Transactions on Electrical and Electronic Engineering  (IEEJ Transactions on Electrical and Electronic Engineering)
巻： 4  号： 5  ページ： 663-667  発行年： 2009年09月 
JST資料番号： W1854A  ISSN： 1931-4973  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 組合せ最適化問題の重要な例であり,モデル化マッチング問題,通信ネットワーク,コンピュータサイエンスなどの分野で多くの適用性を持つモデル化2部部分グラフ問題の求解法について考察した。NP完全問題は,与えられたグラフ中からエッジ数最多の2部部分グラフを見出すことである。本文では,この問題を効率的に解くために,遺伝的操作を確率的に行うのではなく,条件に基づいて行う新しい遺伝的アルゴリズムを提案した。本手法の従来手法に対する優位性を多くの適用例や実験により立証した。

シソーラス用語： 条件付け ,  制約条件 ,  遺伝的アルゴリズム ,  *部分グラフ ,  *グラフ理論 ,  *組合せ最適化問題 ,  解析的解法 ,  *NP完全問題 ,  進化的計算

分類 (1件)： 数理計画法  (KA03030M)

引用文献 (22件)：

• ASRATIAN, AS. Bipartite Graphs and their Applications. 1998, 1
• GAREY, MR. Some simplified NP-complete graph problem. Theoretical Computer Science. 1976, 1, 237-267
• KARP, RM. Reducibility Among Combinatorial Problems. Complexity of Computer Computations. 1972, 85-104
• EVEN, S. NP-completeness of Several Arrangement Problems. 1975
• BONDY, JA. Largest bipartite subgraph in triangle-free graphs with maximum degree three. Journal of Graph Theory. 1986, 10, 477-504

タイトルに関連する用語 (4件)： 遺伝的アルゴリズム ,  部分グラフ ,  問題 ,  求解