イベント情報

Zoomによるオンライン開催

京都大学 学術情報メディアセンター

京都大学 学術情報メディアセンター　宮崎　修一
TEL：075-753-7418
メール：shuichi * media.kyoto-u.ac.jp （*を＠に変えてください）

◆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とするような最大点数部分グラフを探索する問題は最大クリーク問題と呼ばれ、本講演で考える問題は最大クリーク問題を特別な場合として含んでいる。本講演では、距離限定部分グラフの探索問題の計算困難性、近似可能性、入力グラフを限定した場合の計算容易性・困難性について紹介する。