組合せ数学セミナー
発表内容の概要

5/14(金): 上原隆平 (駒沢大学 文学部 自然科学教室)
　Longest Paths in Small Graph Classes
(jointed work with Yushi UNO)

与えられたグラフの中の最長の路を見つける問題を最長路問題と呼ぶ．
与えられたグラフがハミルトン路を持つかどうかを判定する問題は広く研究されている
が，
最長路問題が効率良く解けるグラフクラスに関する研究はほとんどない．
与えられたグラフが木であったとき，最長路問題は線形時間で解くことができる．
まずこの結果を一般化し，木と似た構造を持つグラフクラスについて，
最長路問題が効率良く解けることを示す．
具体的には，以下のグラフについて最長路問題が効率良く解けることを示した．
辺と頂点に重み付けられた木，block graphs, Ptolemaic graphs, cacti．
また，自然な区間表現を持つようなグラフクラスを3つ提案し，
これらのクラス上で最長路問題が効率良く解けることを示す．

--

The longest path problem is to find a longest path in a given graph.
While the graph classes in which the Hamiltonian path problem can be solved efficiently
are widely investigated, few graph classes are known to be solved efficiently
for the longest path problem.
For a tree, a simple linear time algorithm for the longest path problem is known.
We first generalize the algorithm, and show that
the longest path problem can be solved efficiently for weighted trees,
block graphs, ptolemaic graphs, and cacti.
We next propose three new graph classes that have natural interval representations,
and show that the longest path problem can be solved efficiently on the classes.
As a corollary, it is also shown that the problem can be solved efficiently on threshold graphs.
We also show that the longest path problem for interval graphs
can be reduced to the longest path problem for convex graphs.
The complexity of the longest path problem for interval graphs, convex graphs,
and biconvex graphs is remained open.

5/28(金): 室谷浩平 (東京大学大学院情報理工学系研究科数理情報学専攻)
拡張SSAアルゴリズムを用いた3次元多角形メッシュへの電子透かしの埋め込み 　

電子透かしの埋め込みとは，メディアに何らかの構造を付与することによって，
隠したい情報を埋め込む技術のことである．そして，その応用には，
説明の追加，改竄の検出，正規購入者の認証などがある．本研究は，3次元多角形
メッシュに透かしを埋め込む手法を提案する．本手法では，3次元多
角形メッシュの形状を，Singular Spectrum Analysis (SSA)アルゴリズムを用い
てスペクトル分解し，そのスペクトルの係数の中に透かしを埋め込
む．ただし，通常のSSAアルゴリズムは時系列など1次元系列に対して用いられる
手法なので，そのままでは3次元多角形メッシュには適さない．そのた
め本手法では，SSAアルゴリズムを拡張し，3次元多角形メッシュに適用する．こ
の手法によって埋め込まれた透かしは，
相似変換（回転，平行移動，一様拡大縮小）や頂点座標に付加された一様なノイ
ズに対して頑強である．

6/4(金): 八森正泰(筑波大学大学院システム情報工学研究科)
セル複体のacyclic partitionとモース指数

昨年10月のCOMAゼミにおいて，セル複体のファセット・リッジ接続
グラフのある条件下での非巡回的向き付けからセル複体のacyclic 
partitionが導き，これが単体的な場合にはshellabilityと等価で
あり，立方的な場合には各ファセットの「指数」を見ることによっ
てセル複体のベッチ数に関して「モースの不等式」が導かれること
を示していた．今回は，一般の正則セル複体においてacyclic partition
からモースの不等式を導くための「指数」の定義の拡張法を議論し，
また，この議論を最も一般化して扱う枠組も提示する．これは，
Manoj Chariのgeneralized shellingの拡張である．

6/18(金)：牧野和久(大阪大学大学院基礎工学研究科システム創成専攻)
ホーン理論と推論問題

ホーン理論は，人工知能，論理プログラミングなど様々な分野で重要な役割を果たす．
本講演では，ホーン理論の様々な構造的性質，および，アルゴリズムについて述べる．
特に，知識ベースとしてホーン理論を用いたときの演繹推論，仮説推論という２つの
推論問題を，最新の結果も交え，主に計算量の観点から解説する．
また，ホーン理論のその他の話題についても論じる．

7/2(金)：大西健輔(東海大学理学部情報数理学科)
ハフマン木の最適領域の性質について

ハフマン木とは, 葉にデータとその重みを保持し, その重み付き路長和を最小と
する二分木のことである. ハフマン木の組合せ構造は, データの重みに依存する.
ゆえに, 重みの空間は組合せ構造に関係した領域(最適領域と呼ぶ)により分割が
なされる. 本講演では, この分割の性質について述べる.

それぞれの最適領域が凸であり, 非空であることを示した.　また, 2つの領域が
隣接するための組合せ的な必要十分条件を示した.　これらの結果は, アルファ
ベット木に対しても同様に示すことができる.