木幅限定グラフのチャネル割当西関研究室 9561 小幡祐司 2015/10/1 1 論文紹介文献 [1] C. McDiarmid and B. Reed, Channel assignment on graphs of bounded treewidth. , Discrete Math., 273, PP.183-182, 2003. 2015/10/1 2 無線通信におけるチャネル割当混線チャネルA チャネルB 2015/10/1 3 Constraint Matrix Span Problem(CMSP) ,整数B,長さ関数 ･入力：G  V , E　φ : V  1,2,, B　･出力：　(単位 : MHz) ･B  10 ・制約：各辺 xy  E G に対し |φ(d)-φ(c)| =10-1=9 ≧6 8MHz a φ φ y   xy  x   となるように , 各点に 2 １から Bまでの 7 d 10MHz 6 チャネルを割り当てる. b 定理木幅が高々3のグラフに対してもCMSPはNP完全 .[1] 6MHz c 5 1MHz f 2015/10/1 3 2 e 4MHz 2MHz 4 Equality Constraint Matrix Span Problem(ECMSP) ,整数B,長さ関数 ･入力：G  V , E　φ : V  1,2,, B　･出力：　(単位 : MHz) ・制約：各辺 xy  E G に対し･B  10 φ φ y  x    xy  8MHz a となるように , 各点に 2 １から Bまでの 7MHz |φ(d)-φ(c)| =10-1=9 ≧6 7 d 10MHz 6 チャネルを割り当てる. 補題 b Gを道に限定してもECMSPは NP完全．[2] 6MHz 参考文献 [2] S. Whitesides, Algorithmic issues in the geometry of planar linkage movement, Austral. Compu. J.(special issue on algorithms), (1992) 42-50. 2015/10/1 c 5 1MHz f 3 2 e 4MHz 2MHz 5 定理の証明の流れ補題グラフを道Pに限定してもECMSPはNP完全 P １５２３４１５２３４多項式時間変換定理 CMSPは木幅が高々3のグラフに対してもNP完全木幅が３のグラフ２５ 2015/10/1 6 今後の課題・CMSPは木幅が高々３のグラフに対してすらNP完全. ・木幅２のグラフに限定してもNP完全であることを示す．木幅１ 2015/10/1 木幅２直並列グラフ木幅３ 7 2015/10/1 8 木幅３のグラフ K 3 2015/10/1 9 木幅２のグラフ K 2 2015/10/1 10 木幅１のグラフ K 1 2015/10/1 11 木幅 • 木幅 – グラフの木への近さを表す尺度木幅１…木、林 2015/10/1 木幅２…環状の部分構造木幅３…４点の完全グラフ 12