@misc{oai:uec.repo.nii.ac.jp:00005009,
 author = {三柴, 勇太},
 month = {2016-09-23},
 note = {2014, グラフ上の様々な問題について研究が行われているが、一般のグラフについてはNP完全となることが分かっている。しかし、そのような問題でも、ある特定のグラフ族においては多項式時間で解ける場合があることが知られている。ならば、そのグラフ族に「近い」グラフにおいても効率良く解ける可能性がある。そのようなグラフ族に「近い」グラフを表す方法として、辺や頂点の増減をパラメータとして与えるパラメータ化グラフが考えられている。パラメータ化グラフとの例として、あるグラフ族をFとした時、Fに属するグラフに高々k本の辺を追加または削除して得られるグラフからなるグラフ族をそれぞれF+keグラフ、F-keグラフという。　本研究では、パラメータ化グラフの頂点彩色問題を扱う。頂点彩色問題とは、与えられたグラフに対して、隣り合う頂点同士を異なる色になるように最小の色数でグラフの頂点を彩色する問題である。頂点彩色問題は、一般的なグラフに対してはNP完全であるが、二部グラフや比較可能グラフ、splitグラフなどの特定のグラフ族においては多項式時間で頂点彩色問題を解くことができる。そして、これらのグラフに対して高々k本の辺を加えたグラフである二部+keグラフや比較可能+keグラフ、split+keグラフなどのパラメータ化グラフに対する頂点彩色問題の計算複雑さについて研究が行われている。　本研究では、頂点彩色問題を多項式時間で解くことができるグラフ族である置換グラフに対して辺を１本追加したグラフである置換+1eグラフに対する頂点彩色問題を解くアルゴリズムを提案する。そして、この置換+1eグラフに対する頂点彩色問題を解くアルゴリズムの正当性を証明し、そのアルゴリズムが計算時間O(n2logn)時間で解くことができることを示した。},
 title = {置換+1eグラフの頂点彩色問題の計算複雑さ},
 year = {},
 yomi = {ミシバ, ユウタ}
}