大規模2部グラフに対する極大クリーク列挙アルゴリズムの改良と実装

• Item type: SIG Technical Reports(1)
• 公開日: 2003-03-14
• タイトル: 大規模2部グラフに対する極大クリーク列挙アルゴリズムの改良と実装
• タイトル / 言語: en
• タイトル: A Practical Fast Algorithm for Enumerating Cliques in Huge Bipartite Graphs and Its Implementation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 国立情報学研究所
• 著者所属(英): en
• 著者所属(英): National Institute or Informatics
• 著者名: 宇野, 毅明
• 著者名(英): Takeaki, Uno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフ G=(V E) の頂点集合 S に対して，任意の S の頂点間に枝が張られているとき S をクリークとよぶ．また，2部グラフ G=(V1∪ V2 E) の頂点集合 S に対して，任意の S の頂点 v1∈V1 と v2∈V2 に対して枝が張られているならば S を2部クリークとよぶ．本稿では，巨大で疎なグラフの集合の意味で極大なクリークと極大な2部クリークを列挙する，実用的に高速なアルゴリズムを提案する．グラフの次数を Δ とすると，本稿の改良により，極大クリーク１つあたりの計算時間が O(|V||E|) から O(Δ^4) に，極大2部クリークは O(|V||E|) から O(Δ^3) に改善された．さらに，計算機実験により，ある程度ランダムな入力に対しては，1つあたり O(Δ^2) 時間程度しかかからないことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A vertex subset of a graph G=(V, E) is called a clique if any two vertices of S are connected by an edge. A vertex subset of a bipartite graph G=(V1 U V2, E) is called a bipartite clique if any two vertices v1 ∈ V1 and v2 ∈ V2 are connected by an edge. A clique is said to be maximal if it is included in no other clique. In this paper, we propose a practical fast enumeration algorithm for maximal cliques and bipartite maximal cliques of huge sparse graphs. The time complexity per maximal clique is reduced from O(|V||E|) to O(Δ^4), and that of maximal bipartite cliques is reduced from O(|V||E|) to O(Δ^3).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 32(2002-AL-089), p. 1-8, 発行日 2003-03-14
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会