京都大学 数理解析研究所 RIMS 共同研究(公開型) 「計算機科学の数理的基盤とその応用」 (研究代表者: 堀山 貴史)

2023 年度

冬の LA シンポジウム ：2 月 19 日（月）〜2 月 21 日（水）京都大学北部総合教育研究棟 (益川ホール)（〒606-8502 京都市左京区北白川追分町）※ 番号の後ろに S がついている講演は学生発表論文賞の対象

2 月 19 日（月）13:00 - 13:10 オープニング
13:10 - 15:00 一般セッション 1（発表時間 18 分＋質疑応答 4 分）座長:
脊戸 和寿（北海道大学）[1] オフセット付き最大和断片問題のためのデータ構造○ 酒井 義文 (東北大学)[2] 縮約可能変数を持つ項木パターンのマッチングアルゴリズム○ 鈴木 祐介, 内田 智之 (広島市立大学), 正代 隆義 (福岡工業大学),
松本 哲志 (東海大学), 宮原 哲浩 (広島市立大学)[3] 変数が隣接しない正規パターンにより定義される言語の有限和に対するコンパクト性
武田 直人, ○ 内田 智之 (広島市立大学), 正代 隆義 (福岡工業大学),松本 哲志 (東海大学), 鈴木 祐介, 宮原 哲浩 (広島市立大学)[4S] YOMEN の最適質問数◎ 平野 巧稀 (名古屋大学), 木谷 裕紀 (大阪公立大学), 土中 哲秀 (九州大学), 小野 廣隆 (名古屋大学)[5S] 平衡型ジャンケンとその同型性◎ 豊永 明香里 (お茶の水女子大学), 長尾 篤樹 (お茶の水女子大学)

15:00 - 15:15 休憩
15:15 - 16:45 ショートトークセッション 1（発表時間 12 分＋質疑応答 3分）座長: 木村 健斗（成蹊大学）[6S] Graphillion を用いたどうぶつしょうぎと Hex の解析◎ 青木 一敬, 藤原 洋志 (信州大学)[7S] トークンジャンプモデルにおける独立集合の遷移グラフ◎ 佐野 雅弥, 藤原 洋志 (信州大学)[8S] チェイングラフにおける最大マッチング列挙法◎ 鎌田 陽成, 藤原 洋志 (信州大学)[9S] ルーティングゲームの最小コア◎ 小林 知弘, 松井 知己 (東京工業大学)[10S] パレート最適マッチングの多面体的特徴付け ーアンポピュラーマ
ッチングへの適用ー◎ 森山 伊織, 松井 知己 (東京工業大学)[11S] サイズ制約付き連結グラフ分割問題に対する FPT 近似スキーム◎ 山田 秀流, 土中 哲秀 (九州大学)

2 月 20 日（火）9:00 - 10:15 ショートトークセッション 2（発表時間 12 分＋質疑応答 3分）座長: 藤原 洋志（信州大学）[12S] 平面的グラフに対する電力支配集合問題の NP-完全性◎ 澤山 大地, 山田 敏規 (埼玉大学)[13S] Stackelberg 最小費用フロー問題について◎ 北田 秀樹, 山田 敏規 (埼玉大学)[14S] 自転車共有問題: 初期位置の制約緩和と移動速度制約追加の下での解法◎ ハララノフ ヴァレリ, 山田 敏規 (埼玉大学)[15S] 次元が増える box 上のランダムウォークの再帰性と非再帰性◎ 熊本 舟馬 (九州大学), 来嶋 秀治 (滋賀大学), 白井 朋之 (九州大学)[16] モノイド上の有限セルオートマトンの可逆性について○ 井口 修一, 有馬 悠太, 岩永 千寛 (福岡工業大学)

10:15 - 10:30 休憩
10:30 - 12:20 一般セッション 2（発表時間 18 分＋質疑応答 4 分）座長:
小林 靖明（北海道大学）[17S] An Edit Model and Algorithms for Achieving Properties on
Intersection Graphs◎ オノラト ドロゲット ニコラス, 栗田 和宏 (名古屋大学), 土中 哲秀 (九州大学), 小野 廣隆 (名古屋大学)[18S] ラプラシアン行列の固有値に関する木幅の下界とそのさらなる改善
儀間 達也 (名古屋大学), 土中 哲秀 (九州大学), ◎ 野呂 浩平, 小野廣隆, 大舘 陽太 (名古屋大学)[19S] 外 k-平面的グラフにおける木幅の上界の改善
Oksana Firman (Universität Würzburg), Myroslav Kryven(University of Manitoba), ◎ Yuto Okada (Nagoya University),
Alexander Wolff (Universität Würzburg)[20S] グラフ分解に基づく高性能なビール路クエリシステム◎ 杉山 康恭 (名古屋大学), 土中 哲秀 (九州大学), 小野 廣隆 (名古屋大学), 定兼 邦彦 (東京大学)[21S] 頂点被覆とマッチングに対する最適なパラメータ化量子クエリ計算
量◎ 寺尾 樹哉 (京都大学), 森 立平 (名古屋大学)
12:20 - 13:20 昼食休憩
13:20 - 14:26 一般セッション 3（発表時間 18 分＋質疑応答 4 分）座長:
安永 憲司（東京工業大学）[22S] テント符号のランダム生成法◎ 岡田 真明 (九州大学), 来嶋 秀治 (滋賀大学)[23] 非対話型秘密計算の通信量○ 吉田 真紀 (情報通信研究機構)[24] マルチンゲール集中不等式に基づく合意モデルの解析○ 清水 伸高 (東京工業大学), 白髪 丈晴 (中央大学)
14:26 - 14:40 休憩14:40 - 16:08 一般セッション 4（発表時間 18 分＋質疑応答 4 分）座長:栗田 和宏（名古屋大学）[25S] 高さ制約付き LZ 分解

坂内 英夫 (東京医科歯科大学), 舩越 満 (NTT コミュニケーション科学基礎研究所), ディプタラマ ヘンリアン, ◎ 松田 美勇史 (東京医科歯科大学), Simon J. Puglisi (ヘルシンキ大学)[26S] 1 ブロック編集時の最長ボーダークエリと最小カバークエリ◎ 三谷 和暉 (北海道大学), 三重野 琢也 (電気通信大学), 脊戸 和寿,
堀山 貴史 (北海道大学)[27S] フィボナッチ文字列中の極大 α ギャップ付き反復の個数の上界◎ 山根 和真 (北海道大学), 中島 祐人 (九州大学), 脊戸 和寿, 堀山貴史 (北海道大学)[28] Answer Set Programming を用いた圧縮指標の計算○ クップル ドミニク (山梨大学), 番原 睦則 (名古屋大学)
16:08 - 16:20 休憩
16:20 - 16:50 総会＋EATCS ビジネスミーティング

2 月 21 日（水）9:00 - 10:28 一般セッション 5（発表時間 18 分＋質疑応答 4 分）座長: 清水 伸高（東京工業大学）[29S] 直線上におけるロボットによる最小時間荷物配達の NP-困難性◎ 平塚 駿也, 山田 敏規 (埼玉大学)[30] ほぼ線形時間のモバイルエージェント分散配置アルゴリズム○ 首藤 裕一 (法政大学), 柴田 将拡 (九州工業大学), 中村 純哉 (豊橋技術科学大学), 金 鎔煥 (名古屋工業大学), 増澤 利光 (大阪大学)[31] PLS is contained in PLC○ 石塚 天 (富士通株式会社)[32S] 買い手の追加を伴うクリンチングオークション◎ 佐藤 良亮 (東京大学)
10:28 - 10:40 休憩10:40 - 12:08 一般セッション 6（発表時間 18 分＋質疑応答 4 分）座長:長尾 篤樹（お茶の水女子大学）[33S] 整面凸多面体の重なりを持たない辺展開図の数え上げ◎ 塩田 拓海 (九州工業大学), 榎本 優大, 堀山 貴史 (北海道大学), 斎
藤 寿樹 (九州工業大学)[34S] Computing diverse pair of solutions for SAT
儀間 達也 (名古屋大学), 岩政 勇仁 (京都大学), 小林 靖明 (北海道大学), 栗田 和宏, 大舘 陽太 (名古屋大学), ◎ 斉藤 凜 (東北大学)[35] 極小シュタイナー多点対頂点カット列挙の計算困難性
小林 靖明 (北海道大学), ○ 栗田 和宏 (名古屋大学)[36S] カバーリング問題に対するリプシッツ連続アルゴリズム◎ 隈部 壮 (東京大学), 吉田 悠一 (国立情報学研究所)
12:08 - 12:40 LA/EATCS 発表論文賞の投開票と発表・クロージング