2020年度

• 13:00-14:00	【招待講演】宇野 裕之 先生（大阪府立大学） Gourds: a sliding-block puzzle with turning (ISAAC2020 Best Paper Award）
  14:30-15:00	本研究領域の活動報告・今後の予定
  15:00-15:25	計画研究A01班の報告・メンバー自己紹介
  15:25-15:55	計画研究B01班の報告・メンバー自己紹介
  15:55-16:30	計画研究C01班の報告・メンバー自己紹介

   

  2021.03.23 Tue. 13:00-16:30

  公開シンポジウム
  話者： 題目： 概要： 13:00-14:00 【招待講演】宇野 裕之 先生（大阪府立大学） Gourds: a sliding-block puzzle with turning (ISAAC2020 Best Paper Award） 14:30-15:00 本研究領域の活動報告・今後の予定 15:00-15:25 計画研究A01班の報告・メンバー自己紹介 15:25-15:55 計画研究B01班の報告・メンバー自己紹介 15:55-16:30 計画研究C01班の報告・メンバー自己紹介  

  • 公開イベント
  • 2020年度
• 2021.03.23 Tue. 10:30-12:00

  第2回領域会議
  話者： 題目： 概要：

  • 領域内部イベント
  • 2020年度
• ゼロサプレス型二分決定グラフ（ZDD）は集合族を圧縮して表現するデータ構造である．与えられたグラフに対して，パスや全域木などの部分グラフを列挙し，ZDDとして表現するアルゴリズムが知られている．さらに，部分弦グラフや部分区間グラフ，部分平面グラフなどの集合を表すZDDを構築するアルゴリズムが提案されている．構築したZDDはホットスポット検出や選挙区割問題，ペンシルパズルソルバーなどのグラフ最適化問題に応用できる．本発表では，ZDDの基本的な性質を解説した後，ZDDを用いた部分グラフ列挙に関する最近の研究を紹介する．

  2021.02.19 Fri. 15:00-17:00

  第07回セミナー・勉強会
  話者：川原 純（京都大学，B01班） 題目：ZDDを用いた部分グラフ列挙 概要：ゼロサプレス型二分決定グラフ（ZDD）は集合族を圧縮して表現するデータ構造である．与えられたグラフに対して，パスや全域木などの部分グラフを列挙し，ZDDとして表現するアルゴリズムが知られている．さらに，部分弦グラフや部分区間グラフ，部分平面グラフなどの集合を表すZDDを構築するアルゴリズムが提案されている．構築したZDDはホットスポット検出や選挙区割問題，ペンシルパズルソルバーなどのグラフ最適化問題に応用できる．本発表では，ZDDの基本的な性質を解説した後，ZDDを用いた部分グラフ列挙に関する最近の研究を紹介する．

  • セミナー
  • B01
  • 2020年度
• どの隣接2辺も異なる色となるように辺に色を割り当てることをそのグラフの辺彩色といい，特に高々 3 色しか使わないとき 3-辺彩色という．3-辺彩色において，2色で塗られた閉路を1つ選び，その閉路上の色を取り換えることで新しい3-辺彩色が得られる．この操作はケンペによって四色定理の証明のために導入されたもので，現在でも関連問題に対して有力な操作として扱われているものである． 本講演では，3-正則グラフ (どの頂点にも 3本の辺が接続するグラフ) における 3-辺彩色全体の集合に上の遷移を導入し，その到達可能性について議論する．

  2021.02.12 Fri. 15:00-17:00

  第06回セミナー・勉強会
  話者：小関 健太（横浜国立大学，C01班） 題目：3-正則グラフにおける3-辺彩色のケンペ鎖による遷移 概要：どの隣接2辺も異なる色となるように辺に色を割り当てることをそのグラフの辺彩色といい，特に高々 3 色しか使わないとき 3-辺彩色という．3-辺彩色において，2色で塗られた閉路を1つ選び，その閉路上の色を取り換えることで新しい3-辺彩色が得られる．この操作はケンペによって四色定理の証明のために導入されたもので，現在でも関連問題に対して有力な操作として扱われているものである． 本講演では，3-正則グラフ (どの頂点にも 3本の辺が接続するグラフ) における 3-辺彩色全体の集合に上の遷移を導入し，その到達可能性について議論する．

  • セミナー
  • C01
  • 2020年度
• 組合せ遷移は有界モデル検査とどういう関係にあるのかについて聞かれることがあるそうです．このことを議論できるようにするための準備として，有界モデル検査についてはじめて聞く人にも分かるようなレベルで解説する予定です．さらに組合せ遷移の観点では，AIプランニングとの関係も見逃せないと個人的に思うので簡単に解説します．これら２つは古典的な話題です（最近の研究動向には一切触れません）． 一方で，組合せ遷移の理論と実践が交差する，興味深い最近の話題としてネットワークアップデートがあります．現実のネットワークでは設定（例えばあるルータでどのパケットをどこに転送するか）を変更するときに，ネットワークを止めないで安全かつ迅速に更新をすることが求められます．安全性や許される操作などの問題設定がさまざまだったので，理論アルゴリズムの観点から手が出しにくい状況でしたが，最近モデルが整備されアクセスしやすくなっています．そのような中，組合せ遷移の観点からの理論研究はAmiriらを中心に始ったばかりのようです． 横断的な（欲張りな？）テーマであり，十分に説明できないところがあるかもしれません．

  2021.01.22 Fri. 15:00-17:00

  第05回セミナー・勉強会
  話者：戸田 貴久（電気通信大学，B01班） 題目：有界モデル検査，SATプランニング，ネットワークアップデート 概要：組合せ遷移は有界モデル検査とどういう関係にあるのかについて聞かれることがあるそうです．このことを議論できるようにするための準備として，有界モデル検査についてはじめて聞く人にも分かるようなレベルで解説する予定です．さらに組合せ遷移の観点では，AIプランニングとの関係も見逃せないと個人的に思うので簡単に解説します．これら２つは古典的な話題です（最近の研究動向には一切触れません）． 一方で，組合せ遷移の理論と実践が交差する，興味深い最近の話題としてネットワークアップデートがあります．現実のネットワークでは設定（例えばあるルータでどのパケットをどこに転送するか）を変更するときに，ネットワークを止めないで安全かつ迅速に更新をすることが求められます．安全性や許される操作などの問題設定がさまざまだったので，理論アルゴリズムの観点から手が出しにくい状況でしたが，最近モデルが整備されアクセスしやすくなっています．そのような中，組合せ遷移の観点からの理論研究はAmiriらを中心に始ったばかりのようです． 横断的な（欲張りな？）テーマであり，十分に説明できないところがあるかもしれません．

  • セミナー
  • B01
  • 2020年度
• 「組合せ遷移は，離散数学において伝統的に研究されてきた」という立場で，離散数学において どのような組合せ遷移問題が考えられてきたか，紹介する．また，その文脈において，最近勃興 してきた計算理論的側面も含めて，講演者自身の共同研究成果と未解決問題も述べる．その際 に，鍵となる概念は，有限束のハッセ図，凸多面体の1骨格，および，有限群のケーリーグラフ である．これらの概念を，まず，コンピュータ・サイエンスにおける基本的な問題であるソー ティングを例として，説明する．そして，カタラン構造，線形計画法，置換群のような離散数学 における概念と組合せ遷移がどのように関係しているのか，紹介する．

  2020.12.25 Fri. 15:00-17:00

  第04回セミナー・勉強会
  話者：岡本 吉央（電気通信大学，C01班） 題目：組合せ遷移と離散構造 概要：「組合せ遷移は，離散数学において伝統的に研究されてきた」という立場で，離散数学において どのような組合せ遷移問題が考えられてきたか，紹介する．また，その文脈において，最近勃興 してきた計算理論的側面も含めて，講演者自身の共同研究成果と未解決問題も述べる．その際 に，鍵となる概念は，有限束のハッセ図，凸多面体の1骨格，および，有限群のケーリーグラフ である．これらの概念を，まず，コンピュータ・サイエンスにおける基本的な問題であるソー ティングを例として，説明する．そして，カタラン構造，線形計画法，置換群のような離散数学 における概念と組合せ遷移がどのように関係しているのか，紹介する．

  • セミナー
  • C01
  • 2020年度
• 主にグラフクラスと幅パラメータの視点から，独立集合遷移問題についての既存結果や未解決問題を紹介します．

  2020.12.18 Fri. 14:00-16:00

  第03回セミナー・勉強会
  話者：大舘 陽太（名古屋大学，A01班） 題目：独立集合の遷移について 概要：主にグラフクラスと幅パラメータの視点から，独立集合遷移問題についての既存結果や未解決問題を紹介します．

  • セミナー
  • A01
  • 2020年度
• 組合せ遷移のアルゴリズムの手法について，代表的なところをいくつかご紹介します．前回の勉強会に参加していなくても構いません．

  2020.12.11 Fri. 15:00-17:00

  第02回セミナー・勉強会
  話者：伊藤 健洋（東北大学，A01班） 題目：組合せ遷移のアルゴリズム －アルゴリズム手法－ 概要：組合せ遷移のアルゴリズムの手法について，代表的なところをいくつかご紹介します．前回の勉強会に参加していなくても構いません．

  • セミナー
  • A01
  • 2020年度
• 岡本吉央 (C01班代表，電通大教授) が登壇し，本研究領域について解説します．

  組合せ遷移を産業界へ広くアピールする機会になれば幸いです．

  
  「電気通信大学新技術紹介フェア2020秋～今話題の研究テーマを紹介します～」 
  テーマ5 「組合せ遷移アルゴリズムの産業応用に向けて」

  2020.11.25 Wed. 13:30-17:05

  電気通信大学主催 産学官連携イベント
  話者： 題目： 概要：岡本吉央 (C01班代表，電通大教授) が登壇し，本研究領域について解説します． 組合せ遷移を産業界へ広くアピールする機会になれば幸いです． 「電気通信大学新技術紹介フェア2020秋～今話題の研究テーマを紹介します～」  テーマ5 「組合せ遷移アルゴリズムの産業応用に向けて」

  • 公開イベント
  • 2020年度
• アルゴリズム理論の観点から見た「組合せ遷移」について，まずはフレームワーク (問題設定) について説明します．その後，今回は，計算困難性の証明について，いくつかご紹介します．

  2020.11.20 Fri. 15:00-17:00

  第01回セミナー・勉強会
  話者：伊藤 健洋（東北大学，A01班） 題目：組合せ遷移のアルゴリズム －計算困難性の証明－ 概要：アルゴリズム理論の観点から見た「組合せ遷移」について，まずはフレームワーク (問題設定) について説明します．その後，今回は，計算困難性の証明について，いくつかご紹介します．

  • セミナー
  • A01
  • 2020年度