組合せ数学セミナー 特別編(2003.3.20)
発表内容の概要

3/20(木) 13:00〜 : 松井泰子(東海大・理・情報数理)
「変数付きグラフへのグラフの代入の列挙」

  変数と呼ばれる自由度のある頂点をもつ無向全張木G1に対して、
無向全張木G2の代入方法を列挙するアルゴリズムについて考える．
  変数と呼ばれる頂点には、部分グラフを代入することができ，
何も代入されない(辺のみを代入する)事が許されるものとする．
ただし，G1の端点とG2の端点は対応し，G1中の変数を含まない
部分グラフは，G2中の部分グラフと重なるようにする．

  本発表は、列挙アルゴリズム構築の経過報告である．

3/20(木) 15:00〜 : 森口聡子(東工大・情報理工)
「Ｍ凸劣モジュラ流問題のアルゴリズム」

 Ｍ凸関数は, 整数格子点上で定義された関数のクラスとして,
1996年に室田により提案された概念であり，
離散凸解析において中心的な役割を担っている．
Ｍ凸劣モジュラ流問題は，効率良く解くことができる組合せ最適化問題の
最も一般的な枠組みの一つであり，
その特殊ケースとして最小費用流問題や劣モジュラ流問題を含む．
 本発表では, Ｍ凸劣モジュラ流問題を解くアルゴリズムを紹介する．

3/20(木) 17:00〜 : 石関 隆幸(東大・理・情報科学)
「standard pair を用いたいくつかの整数計画問題の解析」

整数計画問題に対して，近年 Gr{\"o}bner 基底や standard pair を用いた計算
代数的手法が研究されている．これらの手法と既存の組合せ的手法の橋渡しを行
うことにより，双方の手法の理解が高まり，新たな構造解析手法やアルゴリズム
の構築が期待される．

本発表ではまず，standard pair を用いて
・行列が単模のときの，双対実行可能基底の数の最大値
を体積の形で与え，それを用いて，
・(トーナメントグラフ上の)最小費用流問題
・(トーナメントグラフ上の)最小費用流問題の双対問題
・輸送問題 (Klee-Witzgall 1968 の別証)
・輸送問題の双対問題 (Balinski-Russakoff 1984 の別証)
・2x...x2x2xN 型多次元輸送問題
・2x...x2xMxN 型多次元輸送問題の双対問題
の実行可能基底の数について，時間の許す限り考察する．