グラフのマッチング彩色における最大色数での彩色方法

• Item type: SIG Technical Reports(1)
• 公開日: 2022-11-10
• タイトル: グラフのマッチング彩色における最大色数での彩色方法
• タイトル / 言語: en
• タイトル: Maximum Number of Colors in Matching Coloring of Graphs and its Coloring Method
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 中央大学理工学研究科
• 著者所属: 中央大学理工学研究科
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Engineering, Chuo University
• 著者名: 豊田, 佳奈子; 田村, 裕
• 著者名(英): Kanako, Toyoda; Hiroshi, Tamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 無線通信におけるチャネル割当とグラフ理論における彩色問題について関連性が示され，様々な研究がされておりその多くは色数の最小値に関するものである．しかしこれらの研究内容を活かし応用していく場合，必要なチャネル数を見積もる為に，Grundy Number と呼ばれる色数の最大値についても考慮する必要がある．マッチング彩色は，高い通信機能を持たないセンサネットワークにおけるチャネル割当てへの応用が期待されている．本研究ではグラフのマッチング辺に順序をつけて色を割当てる貪欲辺彩色において，その彩色色数が最大となる場合における実際の彩色方法について考察する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The relationship between channel assignment in wireless communication and coloring problems in graph theory is well-known. But many of studies are related to the minimum value of the number of colors. When utilizing and applying these research contents in order to estimate the number of channels required, but it is also necessary to consider the maximum value of the number of colors called Grundy Number. Matching coloring is expected to be applied to channel allocation in sensor networks that do not have high communication functions. In this research, we will consider the actual coloring method when the number of colors is maximized in greedy coloring, in which colors are assigned by ordering the matching edges of a graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-190, 号 15, p. 1-4, 発行日 2022-11-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会