【中止】学術情報メディアセンターセミナー「グラフアルゴリズム」

16時30分～17時30分

講演者

小野 廣隆（名古屋大学情報学研究科 教授）

講演題目

グラフのL（2,1）-ラベリングに対するアルゴリズム

講演概要

グラフのk-L（2,1）-ラベリングとは、頂点へのk以下の非負整数の割当てで、距離1の頂点間では2以上、距離2の頂点間では1以上の差があるものを言います。グラフが与えられたとき、k-L（2,1）-ラベリングが存在するような最小のkを求めることは一般にはNP困難であり、多項式時間アルゴリズムが存在するグラフクラスは木などごく一部に限られています。本講演では、木、外平面グラフに対する多項式時間アルゴリズム、単位円グラフに対する多項式時間近似アルゴリズムなどを紹介します。

17時30分～18時30分

講演者

宮野 英次（九州工業大学情報工学研究院 教授）

講演題目

距離限定部分グラフの探索

講演概要

本講演では、与えられたグラフの中から任意の2点間の距離が所望の距離以下であるような部分グラフの中で、出来るだけ点数が多くなるような部分グラフを探索する問題を考えます。任意の2点間の距離を1とするような最大点数部分グラフを探索する問題は最大クリーク問題と呼ばれ、本講演で考える問題は最大クリーク問題を特別な場合として含んでいます。本講演では、距離限定部分グラフの探索問題の計算困難性、近似可能性、入力グラフを限定した場合の計算容易性・困難性について紹介します。