文献

J-GLOBAL ID：201502249343206787   整理番号：15A0585828

ハイパーグラフにおける極大独立集合列挙のためのZDD構築手法

ZDD Construction for Maximal Independent Set Enumeration on Hypergraph

著者 (3件)： 菅谷輝治 (放送大) ,  戸田貴久 (東京電通大) ,  湊真一 (北大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 509(COMP2014 42-51)  ページ： 19-27  発行年： 2015年03月02日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本研究では,ハイパーグラフの極大独立集合を列挙する効率的な手法を提案する。提案手法では,ハイパーグラフの頂点を効率よく削除,復元するためにDancing linksと呼ばれるデータ構造を採用し,合わせて解の索引付けのためにZero-suppressed binary decision diagrams(ZDD)と呼ばれる圧縮手法を用いる。提案手法は,ハイパーグラフの全ての極大独立集合を列挙する厳密解法である。(著者抄録)

シソーラス用語： *超グラフ ,  *集合論 ,  *二分決定グラフ ,  頂点 ,  *データ構造 ,  厳密解 ,  索引作成 ,  計算機シミュレーション ,  表記法 ,  木探索 ,  接続行列
準シソーラス用語： ハイパーグラフ ,  二分決定図 ,  索引付 ,  枝刈り【木探索】

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (17件)：

• Randal E Bryant. Graph-based algorithms for boolean function manipulation. Computers, IEEE Transactions on, Vol. 100, No.8, pp. 677-691, 1986.
• Shin-ichi Minato. Zero-suppressed bdds for set manipulation in combinatorial problems. In Design Automation, 1993. 30th Conference on, pp.272-277. IEEE, 1993.
• Salil Vadhan. The complexity of counting. Undergraduate thesis, 1995.
• Catherine Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity, Vol.9, No. 1, pp.52-72, 2000.
• Ram Nathaniel Krivelevich, Michael and Benny Sudakov. Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Journal of Algorithms, Vol. 41, No.1, pp. 99-113, 2001.

タイトルに関連する用語 (5件)： ハイパーグラフ ,  集合 ,  ZDD ,  構築 ,  手法