拡張極大P-star分割に対する自己安定アルゴリズム

• Item type: National Convention(1)
• 公開日: 2024-03-01
• タイトル: 拡張極大P-star分割に対する自己安定アルゴリズム
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: ソフトウェア科学・工学
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 奈良先端大
• 著者所属: 奈良先端大
• 著者所属: 福井工大
• 著者所属: 奈良先端大
• 著者名: 茶円, 春希; 江口, 僚太; 大下, 福仁; 井上, 美智子
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper introduces a new problem extended maximal P -star partition where maximal p-star decompositions are concurrently constructed for p = 0, 1, . . . , P for a given P . We propose a self-stabilizing algorithm constructing the extended maximal P -star partition of a distributed network. The extended maximal P -star partition is a partition of nodes in a graph such that for any p (≤ P ), maximal p-star decomposition is constructed for a graph excluding nodes belonging to larger stars. Under the unfair distributed daemon, the most general scheduler model, our proposed algorithm converges in at most O(n) rounds with O(P log n)space per process, where n is the number of nodes. Though the extended maximal P -star partition is achieved with a fair composition of maximal p-star decomposition algorithms for p = 0, 1, . . . , P , the proposed algorithm only requires the same space complexity as existing maximal P -star decompoition, that concludes, it drastically reduces space complexity with comparable round complexity compared to a fair composition of existing algorithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00349328
• 書誌情報: 第86回全国大会講演論文集; 巻 2024, 号 1, p. 221-222, 発行日 2024-03-01
• 出版者 / 言語: ja
• 出版者: 情報処理学会