文献

J-GLOBAL ID：201302200338828849   整理番号：13A0873708

超辺の縮約を許した非巡回部分超グラフの効率よい列挙

Efficient Enumeration of Acyclic Hyperedge-Contracted Sub-Hypergraphs in a Hypergraph

著者 (4件)： 和佐州洋 (北大 大学院情報科学研究科) ,  有村博紀 (北大 大学院情報科学研究科) ,  宇野毅明 (国立情報学研) ,  平田耕一 (九州工大 大学院情報工学研究院)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2012  号： 6  ページ： ROMBUNNO.AL-143,NO.6  発行年： 2013年04月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,入力超グラフH=(ν,ε)から超辺縮約をくり返し適用して得られる連結でベルジュ非巡回な部分超グラフの族を考え,そのような部分超グラフすべてを効率よく列挙する初めての多項式遅延と多項式領域列挙アルゴリズムを与える。アルゴリズムは,解となる部分超グラフSの1個あたりO(k^1.5mn)時間とO(N)語の領域で,解を列挙する。ここに,k=|S|であり,N=∥ε∥,m=|ε|,n=|ν|である。そのために,この族に対する還元系列を用いた特徴づけを与える。(著者抄録)

シソーラス用語： *グラフ理論 ,  *超グラフ ,  次元縮小 ,  縮約 ,  高次元 ,  コンパクト多様体 ,  高速アルゴリズム ,  計算理論 ,  計算量
準シソーラス用語： グラフ縮約 ,  多項式時間 ,  多項式時間アルゴリズム ,  反復アルゴリズム ,  連結グラフ

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

タイトルに関連する用語 (4件)： 辺 ,  縮約 ,  巡回 ,  超グラフ