講演名 2016-06-15
グラフ彩色からみた無線通信におけるチャネル数の範囲について
田村 裕(中大), 松本 峻(中大), 中野 敬介(新潟大),
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 無線通信におけるチャネル割当とグラフ理論における彩色問題は古くから関連性が示され,様々な研究がなされてきた.その中で多くの理論的な研究は,割当てるチャネル数を最小としたものである.これは,彩色問題における染色数に対応するからであり,グラフ理論における結果も応用可能であることからである.ただし,チャネル数を最小にするためには,すべてのすでに割当てられているチャネルを再割当する等,実際に適用するには問題が多い.実際には,キャリアセンス等で空きチャネルを探して割当てるため,最悪の場合,チャネル数はどの程度必要であるかが重要であり,この点では,グラフ理論からのアプローチはほとんど見られない.そこで本報告では,代表的な彩色である,点彩色,辺彩色における色数の最大値について考察する.
抄録(英) The relation of channel assignment problems in wireless communications and coloring problems of graph theory is well-known. A channel in the wireless communication is corresponding to a color assigned to a vertex (an edge) in a graph. It is popular to minimize the number of colors assigned to vertices of the graph. However, the maximum number of colors is also important. Because, we may not assign optimal channels all the time. in wireless communication. So, it is important how much channels we set up. We show the upper bounds of colors assigned to some graphs.
キーワード(和) 無線通信 / チャネル割当 / グラフ彩色 / チャネル数の上限
キーワード(英) Wireless communication / Channel assignment / Graph coloring / Upper bound of channels
資料番号 ICTSSL2016-15
発行日 2016-06-07 (ICTSSL)

研究会情報
研究会 ICTSSL
開催期間 2016/6/14(から2日開催)
開催地(和) 東北大学
開催地(英) Tohoku University
テーマ(和) 一般
テーマ(英)
委員長氏名(和) 岡田 和則(NICT)
委員長氏名(英) Kazunori Okada(NICT)
副委員長氏名(和) 田村 裕(中大) / 中野 敬介(新潟大)
副委員長氏名(英) Hiroshi Tamura(Chuo Univ.) / Keisuke Nakano(Niigata Univ.)
幹事氏名(和) 川上 博(NTTドコモ) / 井ノ口 宗成(静岡大)
幹事氏名(英) Hiroshi Kawakami(NTT DoCoMo) / Munenari Inoguchi(Shizuoka Univ.)
幹事補佐氏名(和) 佐藤 翔輔(東北大) / 和田 友孝(関西大)
幹事補佐氏名(英) Shosuke Sato(Tohoku Univ.) / Tomotaka Wada(Kansai Univ.)

講演論文情報詳細
申込み研究会 Technical Committee on Information and Communication Technologies for Safe and Secure Life
本文の言語 JPN
タイトル(和) グラフ彩色からみた無線通信におけるチャネル数の範囲について
サブタイトル(和)
タイトル(英) On the number of channels in wireless networks from the standpoint of graph colorings
サブタイトル(和)
キーワード(1)(和/英) 無線通信 / Wireless communication
キーワード(2)(和/英) チャネル割当 / Channel assignment
キーワード(3)(和/英) グラフ彩色 / Graph coloring
キーワード(4)(和/英) チャネル数の上限 / Upper bound of channels
第 1 著者 氏名(和/英) 田村 裕 / Hiroshi Tamura
第 1 著者 所属(和/英) 中央大学(略称:中大)
Chuo University(略称:Chuo Univ.)
第 2 著者 氏名(和/英) 松本 峻 / Shun Matsumoto
第 2 著者 所属(和/英) 中央大学(略称:中大)
Chuo University(略称:Chuo Univ.)
第 3 著者 氏名(和/英) 中野 敬介 / Keisuke Nakano
第 3 著者 所属(和/英) 新潟大学(略称:新潟大)
Niigata University(略称:Niigata Univ.)
発表年月日 2016-06-15
資料番号 ICTSSL2016-15
巻番号(vol) vol.116
号番号(no) ICTSSL-92
ページ範囲 pp.85-90(ICTSSL),
ページ数 6
発行日 2016-06-07 (ICTSSL)