極大クリーク分割に基づく自己安定クラスタリングアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2008-03-07
• タイトル: 極大クリーク分割に基づく自己安定クラスタリングアルゴリズム
• タイトル / 言語: en
• タイトル: A self-stabilizing clustering algorithm based on maximal clique partition
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学大学院工学研究科情報工学専攻
• 著者所属: 名古屋工業大学大学院工学研究科情報工学専攻
• 著者所属: 名古屋工業大学大学院 工学研究科情報工学専攻
• 著者所属: 名古屋工業大学大学院工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology
• 著者名: 西村, 弘志; 泉, 泰介; 片山, 喜章; 和田, 幸一
• 著者名(英): Hiroshi, Nishimura; Taisuke, Izumi; Yoshiaki, Katakama; Koichi, Wada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿ではグラフを完全部分グラフ（クリーク）に分割する問題（クリーク分割問題）について考える．クリーク分割はアドホックネットワークのクラスタリングなどへの応用があり，分割数が小さい方がよいと考えられるが，分割数を最小とする分割を求めることは NP 完全である． そこで，本稿では分割数を極小とする問題を考え，この問題を解く自己安定アルゴリズムを提案する．ここで提案するアルゴリズムは，マッチングとマージという単純な操作を行う自己安定アルゴリズムを公平な合成により多段階層化することでこの問題を解く．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider a problem to partition a graph into complete subgraphs (cliques), witch is called clique partition problem. This problem is related to some clustering of ad-hoc networks. Since finding the partition such that the number of cliques is minimum is NP-complete, we consider a problem such that the number of cliques is minimal. We propose a self-stabilizing algorithm that solves this problem. Our proposed algorithm consists of multiple layers of two self-stabilizing algorithms which do two simple operations (matching and merging). They are done by "fair composition"
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 24(2008-AL-117), p. 1-8, 発行日 2008-03-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会