グラフのマッチングへの彩色とマルチホップ無線ネットワークにおけるチャネル割当

松本　峻  田村　裕  中野　敬介  仙石　正和  

誌名
電子情報通信学会論文誌 A   Vol.J102-A    No.6    pp.194-200
発行日: 2019/06/01
Online ISSN: 1881-0195
DOI: 
論文種別: 特集論文 (回路とシステム論文小特集)
専門分野: 
キーワード: 
無線通信,  チャネル割当,  グラフ彩色,  マッチング,  

本文: PDF(2.6MB)>>
論文を購入


あらまし: 
無線通信におけるチャネル割当とグラフ理論における彩色問題は古くから関連性が示され，様々な研究がなされてきた．その一つにマルチホップ無線ネットワークとグラフの辺彩色があげられる．無線端末は，センサ等さまざまなものが想定されるため，単純な辺彩色への帰着では，端末の機能を考慮しておらず，現実性のあるモデル化とはならない．そこで本論文では，端末の機能を制限した場合のモデル化として，グラフのマッチングの概念を用いた新たなグラフの彩色問題を提案し，その性質について論ずる．まず，これまでの彩色問題と同様に，最小色数を求めるのは難しいことを示し，最小色数の上限値と幾つかのグラフの族の最小色数についての結果を示す．