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

• Item type: SIG Technical Reports(1)
• 公開日: 2013-02-22
• タイトル: 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
• タイトル / 言語: en
• タイトル: Efficient Enumeration of Acyclic Hyperedge-Contracted Sub-Hypergraphs in a Hypergraph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 国立情報学研究所
• 著者所属: 九州工業大学大学院情報工学研究院
• 著者所属(英): en
• 著者所属(英): Hokkaido University, Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Hokkaido University, Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Department of Artificial Intelligence, Kyushu Institute of Technology
• 著者名: 和佐, 州洋; 有村, 博紀; 宇野, 毅明; 平田, 耕一
• 著者名(英): Kunihiro, Wasa; Hiroki, Arimura; Takeaki, Uno; Kouichi, Hirata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，入力超グラフH = (ν,ε)から超辺縮約をくり返し適用して得られる連結でベルジュ非巡回な部分超グラフの族を考え，そのような部分超グラフすべてを効率よく列挙する初めての多項式遅延と多項式領域列挙アルゴリズムを与える．アルゴリズムは，解となる部分超グラフSの1個あたりO(k1,5mn)時間とO(N)語の領域で，解を列挙する．ここに，k = |S|であり，N = ||ε||，m = |ε|，n = |ν|である．そのために，この族に対する還元系列を用いた特徴づけを与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper we study the problem of enumerating all connected and Berge-acyclic hyperedge-contracted sub-hypergraphs in an input hypergraph. We present the first polynomial delay and polynomial space enumeration algorithm for the problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2013-AL-143, 号 6, p. 1-8, 発行日 2013-02-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会