イベント情報

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

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

Post date:2020/01/21

【開催中止のお知らせ】 (2020年2月27日)
新型コロナウイルスの感染拡大の状況を鑑み、開催中止とさせていただきます。
ご理解のほどよろしくお願いいたします。


京都大学学術情報メディアセンターでは、各分野でご活躍の講師をお招きし、それぞれの研究開発活動の内容や現在抱えている課題についてご紹介いただき、参加者を含めて広く議論を行う機会として、月例セミナーを開催しています。

3月10日の学術情報メディアセンターセミナーでは、名古屋大学の小野廣隆氏と、九州工業大学の宮野英次氏をお招きし、ご講演いただきます。学内外を問わず多数の方のご参加をお待ちしています。

日時 2020/03/10(火)16時30分〜18時30分
会場

京都大学 学術情報メディアセンター南館 2階 202マルチメディア講義室
http://www.kyoto-u.ac.jp/ja/access/campus/yoshida/map6r_ys.html
(上記URLのマップ中、93番の建物です)
※お身体の不自由な方はエレベーターをご利用いただけますので、事務室にお申し付けください。

定員
参加費用 無料
参加申込み 不要
主催

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

お問い合わせ

京都大学 学術情報メディアセンター 宮崎 修一
電話番号:075-753-7418
メール:shuichi * media.kyoto-u.ac.jp (*を@に変えてください)

プログラム

1630分~1730
講演者:小野 廣隆(名古屋大学大学院情報学研究科 教授)
講演題目:グラフのL(2,1)-ラベリングに対するアルゴリズム
講演概要:グラフのk-L(2,1)-ラベリングとは、頂点へのk以下の非負整数の割当てで、距離1の頂点間では2以上,距離2の頂点間では1以上の差があるものを言う。グラフが与えられたとき、k-L(2,1)-ラベリングが存在するような最小のkを求めることは一般にはNP困難であり、多項式時間アルゴリズムが存在するグラフクラスは木などごく一部に限られている。本講演では、木、外平面グラフに対する多項式時間アルゴリズム、単位円グラフに対する多項式時間近似アルゴリズムなどを紹介する。


17時30分~1830
講演者:宮野 英次(九州工業大学大学院情報工学研究院 教授)
講演題目:距離限定部分グラフの探索
講演概要:本講演では、与えられたグラフの中から任意の2点間の距離が所望の距離以下であるような部分グラフの中で、出来るだけ点数が多くなるような部分グラフを探索する問題を考える。任意の2点間の距離を1とするような最大点数部分グラフを探索する問題は最大クリーク問題と呼ばれ、本講演で考える問題は最大クリーク問題を特別な場合として含んでいる。本講演では、距離限定部分グラフの探索問題の計算困難性、近似可能性、入力グラフを限定した場合の計算容易性・困難性について紹介する。

備考
|
イベント情報 過去のイベント
ページトップへ
Copyright © Academic Center for Computing and Media Studies, Kyoto University, All Rights Reserved.