講演抄録/キーワード |
講演名 |
2007-06-29 09:25
部の大きさの比が高々定数倍の孤立2部クリークの列挙 ○宮川博光・伊藤大雄・岩間一雄(京大) COMP2007-19 |
抄録 |
(和) |
グラフ$G=(V,E)$の最大の2部クリークを求める問題や極大の2部クリークを列挙する問題は難しい.クリークでも同様に難しいが,極大孤立クリークの列挙は線形時間ですべて列挙できることが分かっている.本稿では極大孤立2部クリークを列挙する問題を扱う.しかし,極大孤立2部クリークは指数個存在する場合があることが示せるので,二つの部の大きさの比が定数である様な極大孤立2部クリークについて扱う.それらが線形個しか存在しないことを示し,それらをすべて列挙する線形時間アルゴリズムを提案する. |
(英) |
Problems for finding a maximum bipartite clique and enumerating maximal bipartite cliques for graphs are difficult. Although such ploblems are similarly difficult also for cliques, it is known that maximal isolated cliques are enumerated at linear time. In this paper, we deal with maximal isolated bipertite cliques. However, we show that some graphs include a number of exponential maximalisolated bipertite cliques, but the number of maximal isolated bipartite cliques are linear if these part size proportion are bounded by constants. We present an algorithm for enumerating all of them in lineartime. |
キーワード |
(和) |
2部クリーク / 列挙 / アルゴリズム / / / / / |
(英) |
bicliques / enumeration / algorithm / / / / / |
文献情報 |
信学技報, vol. 107, no. 127, COMP2007-19, pp. 9-16, 2007年6月. |
資料番号 |
COMP2007-19 |
発行日 |
2007-06-22 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-19 |