関数に基づく集合分割と有向ハイパーグラフ

• Item type: SIG Technical Reports(1)
• 公開日: 2005-03-17
• タイトル: 関数に基づく集合分割と有向ハイパーグラフ
• タイトル / 言語: en
• タイトル: Partition using functions and directed hypergraphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学サテライトベンチャービジネスラボラトリー
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Satellite Venture Business Laboratory Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Gunma University
• 著者名: 河合, 博之; 柴田, 幸夫
• 著者名(英): Hiroyuki, Kawai; Yukio, Shibata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 二つの集合 X Y および X から Y への二つの関数 f g が与えられるとする．このとき，関数 f g に基づき集合 X を分割する最適問題が存在する．この集合分割問題はダイグラフのある辺彩色問題に対応することが知られている．本研究では，ダイグラフの辺彩色問題という観点から集合分割問題について考察する．また，関数の数を一般化することにより有向ハイパーグラフの辺彩色問題として扱う手法について述べ，彩色数の上界について考察する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given two sets X,Y and two functions f,g from X to Y, there exists an optimization problem with respect to partition of X using functions f and g. It is known that this set partitioning problem is equivalent to an arc-coloring problem of digraphs. We study the set partitioning problem from the point of view of an arc-coloring of digraphs. We also discuss an arc-coloring of directed hyper graphs as a generalization of the number of functions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 26(2004-AL-100), p. 41-46, 発行日 2005-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会