文献

J-GLOBAL ID：201602214215937426   整理番号：16A0023251

二部グラフ中に含まれる弦二部誘導グラフの列挙

Enumeration Algorithm for Chordal Induced Bipartite Graphs of a Bipartite Graph

クリップ

著者 (4件)： 和佐州洋 (北大 大学院情報科学研究科) ,  有村博紀 (北大 大学院情報科学研究科) ,  宇野毅明 (国立情報学研) ,  平田耕一 (九州工大 大学院情報工学研究院)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2015  号： AL-154  ページ： VOL.2015-AL-154,NO.5 (WEB ONLY)  発行年： 2015年09月21日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,弦二部誘導グラフの列挙問題を考察する。二部グラフBが弦二部グラフであるとは,Bに含まれる長さが6以上の任意のサイクルCに対して,C上で隣り合わない2頂点の間に,少なくともひとつの辺があるときをいう。主結果として,与えられた二部グラフに含まれるすべての弦二部誘導グラフを,もれなく重複なく出力する多項式遅延列挙アルゴリズムを与える。(著者抄録)

シソーラス用語： *部分グラフ ,  問題 ,  アルゴリズム理論 ,  計算量 ,  時間計算量
準シソーラス用語： *二部グラフ ,  空間計算量 ,  *弦二部グラフ ,  多項式遅延列挙アルゴリズム ,  列挙問題

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

タイトルに関連する用語 (4件)： 二部グラフ ,  弦 ,  誘導 ,  グラフ