過去の研究概要

[博士課程後期]

グラフの辺連結度増大問題 (Edge-Connectivity Augmentation Problem) [1] の研究に従事しておりました。

この問題は、組合せ最適化問題のひとつで、できるだけ少ない本数の辺付加で、

辺連結度 (edge-connectivity) [2] と呼ばれるグラフの「強度」を増加させる問題です。

私は、特に「分割制約 (partition constraints)」と呼ばれる頂点集合の同一分割内に辺を付加しない制約をもち、

辺連結度を 1 増加させるための高速解法の設計に従事しておりました。

研究会発表や論文等についてご興味を持たれた方は、「Academic Activity」のページをご参照頂けますと幸いです。

参考文献

[1] Egres Open (ハンガリーにある組合せ最適化研究グループの未解決問題に関するサイト (英語))