講演抄録/キーワード |
講演名 |
2015-03-09 16:30
Tangleとイデアル ○山崎浩一(群馬大) COMP2014-51 |
抄録 |
(和) |
本稿では, 先ず台集合$X$とその上の対称劣モジュラ関数$f$に対して,ブール代数上のイデアルを模倣して$(X,f)$上でイデアルを定義する.この$(X,f)$上のイデアルはOum と Seymour により導入された loose tangle と本質的に等しい.その上で, $(X,f)$上の極大イデアルが$(X,f)$上のtangleと等しいことを示す. |
(英) |
In this article, we revisit "tangle" defined on a symmetric submodular function of a set $X$ from the viewpoint of ideals on boolean algebras. For a symmetric submodular function of a set $X$, we first define ideals on $(X,f)$ by simply imitating the definition of ideals on boolean algebras. The defined ideals are essentially the same as "loose tangles" introduced by Oum and Seymour. Then, we show that an ideal $M$ on $(X,f)$ is maximal if and only if $M$ is a tangle on $(X,f)$. |
キーワード |
(和) |
tangle / イデアル / 極大イデアル / 劣モジュラ関数 / / / / |
(英) |
tangle / ideal / maximal ideal / submodular function / / / / |
文献情報 |
信学技報, vol. 114, no. 509, COMP2014-51, pp. 61-64, 2015年3月. |
資料番号 |
COMP2014-51 |
発行日 |
2015-03-02 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2014-51 |