文献

J-GLOBAL ID：201202221383792162   整理番号：12A1585542

グラフ列挙索引化技法の種々の問題への適用

著者 (4件)： 川原純 (JST-ERATO) ,  川原純 (北大) ,  湊真一 (JST-ERATO) ,  湊真一 (北大)
資料名： オペレーションズ・リサーチ
巻： 57  号： 11  ページ： 604-609  発行年： 2012年11月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本記事では,フロンティア法によるs-tパス列挙の技法を,s-tパスだけではなく,全域木やマッチング,集合被覆などにも適用できることを示す。最初に,フロンティア法を用いて,与えられたグラフのすべての全域木の集合や,すべての根付き全域森の集合を表現するZDDを構築する手法について述べる。次に,s-tパスや全域木の場合を一般化する形で,フロンティア法が適用可能な種々の問題を分類,整理して,統一的な視点から述べる。(著者抄録)

シソーラス用語： *二分決定グラフ ,  *スパンニング木 ,  部分グラフ ,  *グラフ理論 ,  *数え上げ理論 ,  超グラフ ,  組合せ問題 ,  ナップサック問題 ,  *高速アルゴリズム ,  索引作成
準シソーラス用語： BDD【グラフ】 ,  *ZDD

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

引用文献 (8件)：

• COUDERT, O. Solving graph optimization problems with ZBDDs. Proceedings of the 1997 European conference on Design and Test, EDTC '97. 1997, 224-228
• HAYASE, K. Output-size sensitiveness of OBDD construction through maximal independent set problem. Lecture Notes in Computer Science. 1995, 959, 229-234
• IMAI, H. Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements and partial orders. Lecture Notes in Computer Science. 1996, 1090, 68-80
• KNUTH, D. E. Combinatorial Algorithms. 2011, Part 1
• 湊真一. BDD/ZDDを用いたグラフ列挙引化技法. オペレーションズ・リサーチ. 2012, 57, 11, 597-603

タイトルに関連する用語 (3件)： グラフ ,  索引 ,  技法