文献

J-GLOBAL ID：201302238718305900   整理番号：13A1340023

Graphillion:巨大なグラフ集合を扱うソフトウェアライブラリ

Graphillion: Software Library for Very Large Sets of Graphs

クリップ

著者 (1件)： 井上武 (JST-ERATO)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 140(IN2013 36-57)  ページ： 43-47  発行年： 2013年07月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： これまでに多くのグラフライブラリが開発されてきたが,それらはひとつのグラフを処理するために設計されている。あるグラフからは指数的な数のサブグラフを取り出せるが,それらを効率的に扱うことはできない。本稿では,Graphillionという巨大なグラフ集合を扱うためのソフトウェアライブラリを提案する。Graphillionは,グラフ集合を「辺の集合の集合」として簡易化してみなすことにより,強力な「集合族演算」を適用可能にし,巨大なグラフ集合を効率的に扱う。また,グラフ列挙アルゴリズムを用いて,単なる集合しか扱えない演算体系にグラフの構造を理解させる。Graphillionは生産性に優れるPython言語のモジュールとして実装されるため,Graphillionを用いたアプリケーションを開発は容易である。パズルソルバと電力網最適化というグラフ集合演算を伴うケーススタディを通し,わずかなコード量で天文学的な数のグラフ(この例では複雑な制約を満たすサイクルや森)を扱い,複雑な問題を解決できることを示す。Graphillionはhttp://graphillion.org/で公開されている。(著者抄録)

シソーラス用語： *ライブラリ【計算機】 ,  *グラフ ,  端部 ,  演算 ,  大規模系 ,  *数え上げ理論 ,  アルゴリズム ,  生産性 ,  モジュール構造 ,  事例研究 ,  閉路
準シソーラス用語： *グラフライブラリ ,  グラフ列挙アルゴリズム ,  集合族演算 ,  森【グラフ】 ,  辺

分類 (3件)： 計算機システム開発  (JD02010R) ,  グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： グラフ ,  集合 ,  ソフトウェアライブラリ