06 2020/07 08
28293001020304
05060708091011
12131415161718
19202122232425
26272829303101
Click セミナー

過去のセミナー

開催日2019年5月22日(水曜日)
開催時間15時00分-16時00分
発表者和佐 州洋 
発表者の紹介国立情報学研究所
タイトルKempe-exhcageの下でのグラフ彩色遷移問題 
発表の概要
グラフk彩色問題とは,与えられたグラフGを隣接する頂点が同じ色にならないようにk色で塗り分けられるかを問う問題である.本発表では,この決定問題に対する遷移問題を考える.具体的にはGに対する2つの彩色αとβが与えられた時に,kempe-changeの下で,k彩色を常に保ちながらαからβを得られるかという問題である.ここでkempe-changeとは,ある2色に着目し,その色で塗られた頂点から誘導されるグラフを考え,そのグラフの一つの連結成分を取り出し,その成分内の色を入れ替えるという操作である.この時,kempe-changeした彩色は正しい彩色となっている.本発表では,グラフk彩色遷移問題の入力グラフが(1)パスの時に多項式時間で解けること,ならびに,(2)星の時にNP-完全であることについて述べる.
本研究は,Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka
Mizuta, Moritz Muehlenthaler, Akira Suzukiらとの共同研究である.
開催場所VBL301B
接続サイト神田ラボ,京大ラボ