| Item type |
SIG Technical Reports(1) |
| 公開日 |
2015-12-08 |
| タイトル |
|
|
タイトル |
大規模グラフにおける擬似クリーク厳密解全列挙に関する考察 |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
北海道大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
北海道大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
北海道大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
電気通信大学先進アルゴリズム研究ステーション |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Hokkaido University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Hokkaido University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Hokkaido University |
| 著者所属(英) |
|
|
|
en |
|
|
Advanced Algorithms Research Laboratory, The University of Electro-Communications |
| 著者名 |
大久保, 好章
ジェイ, 泓杰
原口, 誠
富田, 悦次
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本報告では，著者等が先に提案した，所与のグラフにおける擬似クリークの全列挙問題に対する高速アルゴリズムの有効性を実験的に検証する．抽出対象とする擬似クリークは，それを構成する各頂点毎に非隣接上限数を定めた k-Plex モデルに対し，十分な密度を保証するための隣接下限数を新たな制約として課した j- 核性 k-Plex であり，j- 核計算の単調性を利用することで，探索処理における不要な探索枝の展開が強力に抑制される．実験では，80 万超頂点のウェブグラフを含むネットワークに対して，最新の極大 k-Plex 列挙システムとの比較を行い，計算時間と解の品質の観点から本システムの有効性を確認する． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN10505667 |
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS）
巻 2015-MPS-106,
号 6,
p. 1-6,
発行日 2015-12-08
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8833 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-MPS15106006.pdf (985.6 kB)
