超辺の縮約を許した非巡回部分超グラフの効率よい列挙 Efficient Enumeration of Acyclic Hyperedge-Contracted Sub-Hypergraphs in a Hypergraph

この論文にアクセスする

この論文をさがす

抄録

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

収録刊行物

  • 研究報告アルゴリズム(AL)

    研究報告アルゴリズム(AL) 2013-AL-143(6), 1-8, 2013-02-22

各種コード

  • NII論文ID(NAID)
    110009550139
  • NII書誌ID(NCID)
    AN1009593X
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • データ提供元
    NII-ELS  IPSJ 
ページトップへ