第8回研究会

第8回研究会を以下の通り開催いたしました．

• 日時：2016年 10月 15日 (土) 12時30分〜
• 会場：新潟大学 五十嵐キャンパス 理学部A棟5階大セミナー室 (A523)
  アクセス：http://www.sc.niigata-u.ac.jp/sc/outline/accessmap.html
• 講演者１：鈴木 有祐 氏 (新潟大学理学部)
  • 題目：再埋蔵的視点から見たグラフの1-交差埋め込み
  • 概要：位相幾何学的グラフ理論においては，閉曲面上に辺の交差なく埋め込まれた グラフが研究対象となることがほとんどである．これらのグラフは一般的に``グラフ・マイナー理論''と相性が良く，従来の研究はこれらに依存するものが多い．しかし，``埋め込み''の条件を多少緩和しただけである1-交差埋め込みはこれらの手法で扱えないクラスであることが知られており，そのコントロール方法は未だに未知な部分が多い．本講演においては，1-交差埋め込みの方法そのものから議論を行う（1-交差埋め込みの再埋蔵）ことで明らかになる事実を紹介する．
• 講演者２：平井 広志 氏 (東京大学大学院情報理工学系研究科)
  • 題目：グラフ上の離散凸関数について
  • 概要：離散凸解析は，マトロイド・劣モジュラ関数に端を発する整数格子上の凸関数の理論であり，M凸関数(M^{\natural}凸関数)とL凸関数(L^{\natural}凸関数)が中心的や役割を演ずる．ところで，実はL^{\natural}凸関数は，整数格子をグリッドグラフ，さらには，ツリーの直積におきかえても自然に定義できる．本講演では，そのようなL^{\natural}凸関数のグラフ的な拡張と計算複雑度解析・アルゴリズム設計への応用について講演者の最近の研究を紹介する．

---

戻る