講演抄録/キーワード |
講演名 |
2017-10-27 14:30
線形枝幅と単項イデアル ○藤田顕光・山崎浩一(群馬大) COMP2017-23 |
抄録 |
(和) |
枝幅は良く知られたグラフパラメータの一つであり, グラフから台集合$X$と対称劣モジュラ関数$f$の組$(X,f)$上へのパラメータとして拡張されている.
また, ブール代数上のイデアルを拡張した$(X,f)$上のイデアルと$(X,f)$上の枝幅が双対関係にあることが知られている. 本稿では"単項イデアル"という概念を導入し, その単項イデアルが枝幅のパス版である"線形枝幅"と双対関係にあることを示す. また, 極大な単項イデアルの特徴づけを行う. |
(英) |
Branch-width is a well studied graph parameter, and it was extended into parameter on a connectivity system. Linear-width is also a parameter on a connectivity system, which can be thought of as path version of branch-width. In this report, we introduce a sort of ideal on a connectivity system which we call single ideal and show a duality between single ideal and linear-width. We also give a characterization of maximal single ideal. |
キーワード |
(和) |
枝幅 / イデアル / 線形枝幅 / 単項イデアル / / / / |
(英) |
branch-width / ideal / linear-width / single ideal / / / / |
文献情報 |
信学技報, vol. 117, no. 269, COMP2017-23, pp. 21-27, 2017年10月. |
資料番号 |
COMP2017-23 |
発行日 |
2017-10-20 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2017-23 |