| 講演名 | 2004/4/15 Comparability supergraphを用いた最大重みクリーク問題の厳密解法 山口 一章, 榊原 芳恵, 増田 澄男, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Comparability supergraphを用いて,任意の無向グラフの最大重みクリークの上界を計算する方法を示す.その方法は,彩色を上界として用いる分枝限定法に基づく最大クリーク問題の解法を,最大重みクリーク問題の解法へと自然な形で拡張する.提案法では限定操作においてcomparability supergraphを用いる.計算機実験を行い,提案法の有効性と問題点について調べた結果を示す. |
| 抄録(英) | We show a method for calculating the upper bound of the weight of the maximum weighted clique problem with using comparability supergraphs. With our method, many algorithms for the maximum cadinality clique problem with using the branch-and-bound technique based on coloring are naturally extended to algorithms for the maximum weighted clique problem. Our method uses the maximum weighted clique in a comparability supergraph of the given graph at the bounding stage. We investigate the efficiency and the problems of our method some with some computational experiments. |
| キーワード(和) | 分枝限定法 / 頂点彩色 / comparability graph / transitive orientation |
| キーワード(英) | branch-and-bound / vertex coloring / comparabilitv graph / transitive orientation |
| 資料番号 | COMP2004-4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/4/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | Comparability supergraphを用いた最大重みクリーク問題の厳密解法 |
| サブタイトル（和） | |
| タイトル（英） | An Exact Algorithm for Solving the Maximum Weighted Clique Problem with Using Comparability Supergraphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分枝限定法 / branch-and-bound |
| キーワード(2)（和/英） | 頂点彩色 / vertex coloring |
| キーワード(3)（和/英） | comparability graph / comparabilitv graph |
| キーワード(4)（和/英） | transitive orientation / transitive orientation |
| 第 1 著者 氏名（和/英） | 山口 一章 / Kazuaki YAMAGUCHI |
| 第 1 著者 所属（和/英） | 神戸大学工学部 Faculty of Engineering, Kobe University |
| 第 2 著者 氏名（和/英） | 榊原 芳恵 / Yoshie SAKAKIBARA |
| 第 2 著者 所属（和/英） | 神戸大学自然科学研究科 Kobe University Graduate School of Science and Technology |
| 第 3 著者 氏名（和/英） | 増田 澄男 / Sumio MASUDA |
| 第 3 著者 所属（和/英） | 神戸大学工学部 Faculty of Engineering, Kobe University |
| 発表年月日 | 2004/4/15 |
| 資料番号 | COMP2004-4 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 16 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |