イベント情報

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

学術情報メディアセンターセミナー「グラフアルゴリズム」(オンライン開催)

Post date:2021/10/08

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

11月16日の本セミナーでは、名古屋大学の小野廣隆氏と、九州工業大学の宮野英次氏に講演いただきます。学内外を問わず多数の方のご参加をお待ちしています。

日時 2021/11/16(火)16時30分〜18時30分
会場

Zoomによるオンライン開催

定員
参加費用 無料
参加申込み 以下のフォームから事前にお申し込みください。【申込期限:11月10日(水)】
開催が近づきましたら、メールにてZoomの接続情報をお知らせいたします。
https://forms.gle/jWZkgouYW2fGUh2s6
主催

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

お問い合わせ

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

備考
|
ページトップへ
Copyright © Academic Center for Computing and Media Studies, Kyoto University, All Rights Reserved.