離散システム研究部会のホームページへようこそ!
離散システム研究部会は[[日本応用数理学会:http://www.jsiam.org/]]の研究部会です.

内容はこれから増やしていきますが,
[[関連会議]]の案内などを中心に,
離散システムに関する事柄の解説などを増やしていきたいと思います.
いつまで経っても完成しないけれど,建設中でも十分美しい[[サグラダ・ファミリア>WikiPedia.ja:サグラダ・ファミリア]]を目標とします.
よろしくお願いいたします.

----

*[[日本応用数理学会 2013年度 年会:http://jsiam2013.kyushu-u.ac.jp/]] [#sdd3b3ba]
離散システム研究部会オーガナイズドセッション

**9月9日 602会議室 9:30-10:50 研究部会OS 離散システム(1) [#m0b67bd1]

***9112 閉曲面上のグラフにおけるマッチング拡張性のための距離条件について/◯藤沢 潤, Aldred, Robert E.L., 太田 克弘 [#n2c42023]
***9112 閉曲面上のグラフにおけるマッチング拡張性のための距離条件について/◯藤沢 潤, Aldred, Robert E.L., 太田 克弘 [#n2c42023]~ [#sec6c806]
グラフGのマッチングMに対し、GがMを含む完全マッチングを持つ時、MはGにおいてextendableであると言う。Plummerは頂点数が8以上の平面グラフが必ずextendableでないような3辺からなるマッチングを持つことを示した。一方、平面上の5-連結三角形分割では、互いに距離が離れている3辺のマッチングがextendableになることが知られている。本講演では、平面・トーラス・クラインボトル上の5-連結三角形分割における、どの2辺も距離が離れているようなマッチングのextendabilityに関する結果を紹介する。

***9108 次数を制限した全域木について/◯松村 初 [#ye220255]
***9108 次数を制限した全域木について/◯松村 初 [#ye220255]~ [#y2e6df95]
グラフの各頂点から出ている辺の本数を「次数」と呼ぶ。グラフの全域木で、最大の次数が制限されたものが存在するための条件について、これまで数多くの研究がなされてきた。本講演では、これまでの研究を紹介し、最新の結果についても述べる。

***9105 球面上の統計的実験計画法と立体求積公式/◯平尾 将剛, 澤 正憲 [#a8043776]
***9105 球面上の統計的実験計画法と立体求積公式/◯平尾 将剛, 澤 正憲 [#a8043776]~ [#e3a7fc24]
統計的実験計画法とは,有限個のデータから実験全体の特徴を巧く捉えるために,どこでデータを観測すれば良いか,またその各点でどれだけ観測するかを決定する方法である.本講演では実験計画法と数値積分法の一つである立体求積公式を統一的に扱い,それらを陽的に決定する方法について紹介する.

***9106 Optimal equi-difference conflict-avoiding codes of odd length and weight 3/林 怡伶, ◯三嶋 美和子, 佐藤 潤也, 神保 雅一 [#a0525f63]
***9106 Optimal equi-difference conflict-avoiding codes of odd length and weight 3/林 怡伶, ◯三嶋 美和子, 佐藤 潤也, 神保 雅一 [#a0525f63]~ [#w34bd22e]
重み3かつ奇数符号長の等差衝突回避符号の最大符号語数を求める問題を、符号長を法とする剰余環における2の位数に関する問題に帰着させ、そこから得られるいくつかの性質と、それらを用いて得ることのできる明示的な最適符号のシリーズを示す。

**9月9日 602会議室 11:00-12:20 研究部会OS 離散システム(2) [#fcbba6f2]

***9126 混合整数二次錐計画法を用いた回帰式の変数選択/◯宮代 隆平, 高野 祐一 [#q3d0f53a]
***9126 混合整数二次錐計画法を用いた回帰式の変数選択/◯宮代 隆平, 高野 祐一 [#q3d0f53a]~ [#e4baf3f9]
統計学の回帰分析において,変数選択は重要な課題である.本発表では,赤池情報量規準をはじめとするいくつかの代表的な情報量規準を考え,それらを最小にする変数選択問題が混合整数二次錐計画問題として定式化できることを示す.

***9137 木距離を冪として持つパラメータ行列の行列式と多変数2次安定多項式/平井 広志, ◯矢部 顕大 [#f4ebea07]
***9137 木距離を冪として持つパラメータ行列の行列式と多変数2次安定多項式/平井 広志, ◯矢部 顕大 [#f4ebea07]~ [#ob9f1101]
木距離 D = (Dij) に対し,ij 成分が変数 t の Dij乗となる行列を考える.その行列の行列式の簡潔な組合せ論的公式を与える.応用として,対応する2次型式は,冪級数体上における安定多項式となることを示す.M凸関数との関連も述べる.

***9074 Packing non-zero A-paths via matroid matching/谷川 眞一, ◯山口 勇太郎 [#lb77e848]
***9074 Packing non-zero A-paths via matroid matching/谷川 眞一, ◯山口 勇太郎 [#lb77e848]~ [#qd0ed2ee]
Packing non-zero A-pathsは点素パスパッキング問題の一種であり,一般グラフのマッチング問題と2点間パスパッキング問題の共通の一般化となるMaderのS-path問題や,奇数長の点素A-pathパッキング問題などを含んでいる.この問題を,代表的な離散最適化問題であるマトロイド・マッチング問題に帰着して考えることで,良い特徴付けが導かれることを示す.

***9128 競合者がいるネットワーク上の影響伝播モデル/◯垣村 尚徳, 河原林 健一 [#y125d14f]
***9128 競合者がいるネットワーク上の影響伝播モデル/◯垣村 尚徳, 河原林 健一 [#y125d14f]~ [#m94c39a3]
影響伝播モデルとは,ネットワーク上での噂や宣伝の拡がりをモデル化したものである.本講演では,ネットワーク上に競合者がいる場合にモデルを拡張し,そのモデル上で自身の影響力を最大化するための近似アルゴリズムを与える.


*過去の活動 [#fc7b382c]

**日本応用数理学会 2013年 研究部会連合発表会(東洋大学白山キャンパスにて) [#sa7950a4]
離散システム研究部会オーガナイズドセッション(2013年3月14日木曜日)

**離散システム(1) 14:40〜16:00 [#r074f2a1]

セッション1 14:40--16:00 座長 宮本 裕一郎(上智大学)

***グラフの彩色多項式 14:40--15:00 [#s84abcbb]
 ○中田有紗(お茶の水女子大学大学院),萩田真理子(お茶の水女子大学大学院)

***擬似乱数の評価方法の検証 15:00--15:20 [#t9ccaa85]
 ○高橋絢那(お茶の水女子大学大学院),萩田真理子(お茶の水女子大学大学院)

***情報理論的暗号理論について 15:20--15:40 [#i4c821c9]
 ○四方順司(横浜国立大学)

***任意の制限がシェラブルな単体的複体と純骨格 15:40--16:00 [#e05129a6]
 ○八森正泰(筑波大学大学院),柏原賢二(東京大学大学院)


**離散システム(2) 16:10〜17:30 [#n07e1e8d]

セッション2 16:10--17:30 座長 萩田 真理子(お茶の水女子大学大学院)

***安定結婚問題における最大最適選好マッチングの端点集合の一意性 16:10--16:30 [#idd750fc]
 ○平川瑞樹,山内由紀子,来嶋秀治,山下雅史(九州大学)

***正規圧縮距離を用いたクラスタリング法の実装 16:30--16:50 [#z5b7d60f]
 ○久保浩平,山内由紀子,来嶋秀治,山下雅史(九州大学)

***一般のグラフにおける極大性をもつバリアの標準構造 16:50--17:10 [#mf10e3d0]
 ○喜多奈々緒(慶應義塾大学大学院)

***周期グラフのl1埋め込みについて 17:10--17:30 [#te0f5dab]
 ○夫紀恵(東京大学大学院)


**[[日本応用数理学会 2012年度 年会:http://www.oishi.info.waseda.ac.jp/~jsiam2012/]] [#f64bd7ae]
離散システム研究部会オーガナイズドセッション

**8月29日 会場B 9:00-10:20 研究部会OS 離散システム(1) [#xf447910]

***グラフの不変量と閉路の存在について [#ffaae819]
◯山下登茂紀(近畿大学理工学部)~
グラフがハミルトン閉路を部分構造としてもつための条件に関する研究は盛んに行われており,多くの条件が知られている.本講演では,最近我々によって発見された規則性のある次数和条件について述べる.

***車両配送問題の多項式時間で解けるクラスとその計算量 [#ca7065a9]
◯小田芳彰(慶應義塾大学理工学部)~
巡回セールスマン問題の多項式時間で解けるクラスについてはさまざまな研究がなされてきたが,ここでは,この問題の一般化となる車両配送問題について考える.両問題の類似点,あるいは差異を見るとともに,その計算量についても述べる.

***MacWilliams恒等式による擬似乱数列の下位ビットの分布計算 [#dd8af23f]
◯原本博史(愛媛大学), 松本眞(東京大学), 西村拓士(山形大学), 大塚祐樹(広島大学)~
本発表ではラグ付きFibonacci法による擬似乱数生成法について、下から2-6ビット目それぞれの0-1分布を、符号理論に現れるMacWilliams恒等式を用いて正確に計算し、安全/危険なサンプルサイズを評価した結果を紹介します。

***GF(2)上線形な擬似乱数生成法による並列乱数生成 [#j18560a2]
◯西村拓士(山形大学)~
GF(2)上の線形な生成式による擬似乱数生成法の設計方法について説明を行う。さらに、このタイプの生成法を用いた擬似乱数の並列発生方法について紹介する。

**8月29日 会場B 10:30-11:50 研究部会OS 離散システム(2) [#q5c5bd1e]

***SimRankを用いた協調フィルタリング [#yd7afd0e]
◯井上綾香(上智大学), 宮本裕一郎(上智大学)~
協調フィルタリングとグラフ理論ベースの類似度指標SimRankを利用した商品推薦法を提案する.多品種少量購入データを含む多様なデータにも対応できるのが特徴である.実データに適用した結果も報告する.

***Graph isomorphism problem for graphs of small connected-path-distance-width [#i887c5d7]
◯大舘 陽太(北陸先端科学技術大学院大学)~
We show that Graph Isomorphism problem (GI) can be solved in O(n^2) time for graphs of bounded connected-path-distance-width, where n is the number of vertices.

***グラフ再構築に関する話 [#hf190cb4]
◯清見礼(横浜市立大学)~
グラフ理論の有名な未解決問題であるグラフ再構築予想に関して、グラフクラスを限ったうえでアルゴリズム的な話も交えながら考察する。

***不確実な最適化問題に対するロバスト最適化法 [#n75689d8]
◯武田朗子(慶応義塾大学)~
不確実性を含んだ最適化問題のモデル化とその解法としてロバスト最適化法が提案されて以来,解法研究も進み,適用先も広範囲に広がっている.本発表では,ロバスト最適化を簡単に紹介し,機械学習分野への適用例を報告したい.

**[[日本応用数理学会 2012年 研究部会連合発表会:http://www.comfos.org/jp/Y2011/JSIAM-AG/]] [#qe7bbbb2]
離散システム研究部会オーガナイズドセッション(2012年3月8日木曜日【会場 E】)

***[DS-1] グラフの分散彩色の評価 13:30〜13:50 [#m067150d]
萩田真理子 (お茶の水女子大学大学院), 〇菊池智子 (お茶の水女子大学大学院), 山口真実 (お茶の水女子大学大学院)

***[DS-2] モジュラリティの上界値算出 13:50〜14:10 [#p9d23d73]
〇宮内 敦史 (上智大学), 宮本 裕一郎 (上智大学)

***[DS-3] 指数2の混合方程式を導く回路の構造的特徴付け 14:10〜14:30 [#eaf127e1]
〇高松 瑞代(中央大学)

***[DS-4] 制約付きフィードバック点集合問題に対する固定パラメータ・アルゴリズム 14:30〜14:50 [#s8f0fb14]
〇垣村尚徳(東京大学), 河原林健一(国立情報学研究所)


**[[日本応用数理学会 2010年度 年会:http://jsiam2010.mims.meiji.ac.jp/]] [#d4317149]
***離散システム研究部会オーガナイズドセッション [#vf62f972]
9月6日(月) 14:10--15:30~
会場D(16階1163教室)~

****配属人数下限付き学生ープロジェクト割当問題 [#x122e178]
○神山 直之(中央大学)

****グラフの分散彩色アルゴリズム [#b0b0e3f5]
○山口 真実(お茶の水女子大学),萩田真理子(お茶の水女子大学)

****Enumerating All Rooted Including k Leaves [#nb5e1c59]
石川雅信(群馬大学), ○山中克久(電気通信大学), 大舘陽太 (東北大学), 中野眞一 (群馬大学) 

****制約付き t-マッチングとジャンプシステム: Cunningham の予想の証明 [#pe463e20]
小林佑輔 (東京大学), Jacint Szabo(Eotvos University), ○高澤兼二郎(京都大学) 

----
主査:[[岩田覚]]~
幹事:[[宮本裕一郎]],萩田真理子,平井広志