| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-07-19 16:25 ［招待講演］フロンティア法：BDD/ZDDを用いた高速なグラフ列挙索引化の技法 ○湊 真一（北大/JST）  IN2012-38 |
|
| 抄録 | （和） | 「論理」や「集合」を始めとする様々な離散構造を統合的に演算処理する技法を体系化し，分野横断的かつ大規模な実問題を高速に処理する技術基盤を構築することを目標として「JST ERATO湊離散構造処理系プロジェクト」が発足し，約2年9ヶ月が経過した．この間，多くの興味深い研究成果が得られ始めているが，その中でも，種々の制約条件を満たすグラフ構造をBDD/ZDDを用いて全列挙して索引化する技法（通称フロンティア法）は，Knuthが近年示したパス列挙アルゴリズムSimpathをさらに一般化したものであり，多くの実用的な問題で従来より桁違いに優れた性能を示すことから，今後の発展が大いに期待される．本講演では，この新しいグラフ列挙索引化アルゴリズムの概要を解説し、情報ネットワークに関連する応用研究についても述べる． |
| （英） | Discrete structure manipulation is a fundamental technique for many problems solved by computers. Recently, BDD/ZDD attracts a great deal of attention, because it efficiently manipulates basic data structures such as logic and sets. In order to organize an integrated method of algebraic operations for manipulating various types of discrete structures, and to construct standard techniques for efficiently solving large-scale and practical problems in various fields, JST started a new project: ERATO MINATO Discrete Structure Manipulation System Project on 2009 and now it is in the third year. Currently, one of the most interesting research topic of our project is ``flontier-based method,'' a very efficient BDD/ZDD-based algorithm for enumerating and indexing all the subset of a graph to satisfy various kinds of constraints. In this talk, we present overview of the flontier-based methods and recent research activities related to information network techniques. | |
| キーワード | （和） | ERATO / 離散構造処理系 / BDD / ZDD / フロンティア法 / パス列挙 / グラフアルゴリズム / |
| （英） | ERATO / discrete structure manipulation system / BDD / ZDD / flontier-based method / path enumeration / graph algorithm / | |
| 文献情報 | 信学技報, vol. 112, no. 134, IN2012-38, pp. 31-36, 2012年7月. | |
| 資料番号 | IN2012-38 | |
| 発行日 | 2012-07-12 (IN) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2012-38 |
|
| 研究会情報 | |
| 研究会 | IN NV |
| 開催期間 | 2012-07-19 - 2012-07-20 |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido Univ. |
| テーマ（和） | 新世代・次世代ネットワーク，ネットワークとシステムの仮想化，仮想化環境の管理・監視，オーバーレイ，IPv6ネットワーク，フォトニックネットワークおよび一般 |
| テーマ（英） | New/Next Generation Network, Network/System Virtualization, Management/Monitoring for Virtualization Environments, Overlay, IPv6 Networks, Photonic Network, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2012-07-IN-NV |
| 本文の言語 | 日本語 |
| タイトル（和） | フロンティア法：BDD/ZDDを用いた高速なグラフ列挙索引化の技法 |
| サブタイトル（和） | |
| タイトル（英） | Frontier-based Method: Efficient Graph Enumeration and Indexing Using BDDs/ZDDs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ERATO / ERATO |
| キーワード(2)（和/英） | 離散構造処理系 / discrete structure manipulation system |
| キーワード(3)（和/英） | BDD / BDD |
| キーワード(4)（和/英） | ZDD / ZDD |
| キーワード(5)（和/英） | フロンティア法 / flontier-based method |
| キーワード(6)（和/英） | パス列挙 / path enumeration |
| キーワード(7)（和/英） | グラフアルゴリズム / graph algorithm |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 湊 真一 / Shin-ichi Minato / |
| 第1著者 所属（和/英） | 北海道大学/JST ERATO (略称： 北大/JST) Hokkaido University/JST (略称： Hokkaido Univ./JST) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-07-19 16:25:00 |
| 発表時間 | 45分 |
| 申込先研究会 | IN |
| 資料番号 | IN2012-38 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.134 |
| ページ範囲 | pp.31-36 |
| ページ数 | 6 |
| 発行日 | 2012-07-12 (IN) |
[研究会発表申込システムのトップページに戻る]