文献

J-GLOBAL ID：201802263100127186   整理番号：18A0564356

グラフに含まれる大きな内周を持つ部分グラフの効率良い列挙

Efficient Enumeration of Subgraphs with Large Girth

著者 (5件)： 栗田和宏 (北大 大学院情報科学研究科) ,  CONTE Alessio (Universit di Pisa, Pisa, ITA) ,  和佐州洋 (国立情報学研) ,  宇野毅明 (国立情報学研) ,  有村博紀 (北大 大学院情報科学研究科)
資料名： 情報処理学会全国大会講演論文集
巻： 80th  号： 1  ページ： 1.347-1.348  発行年： 2018年03月13日 
JST資料番号： S0731A  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 内周はグラフに含まれる最小の閉路長である。本論文では,内周がk以上の部分グラフを解1つあたりO(n)時間より効率よく列挙するアルゴリズムを与える。このアルゴリズムの単純な拡張により,k以上の内周を持つ重み付きグラフの部分グラフや非連結な部分グラフの列挙も可能である。(著者抄録)

シソーラス用語： *グラフ ,  *部分グラフ ,  *長さ ,  *閉路 ,  *効率 ,  最小値 ,  *目録作業 ,  アルゴリズム ,  重みづけ
準シソーラス用語： 円周ピッチ ,  *内周

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (2件)：

• T. H. Cormen. Introduction to algorithms. MIT press, 2009.
• A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413-423, 1978.

タイトルに関連する用語 (2件)： グラフ ,  内周