WEKO3
アイテム
単純<i>b</i>-マッチングのDulmage-Mendelsohn分解
https://ipsj.ixsq.nii.ac.jp/records/174612
https://ipsj.ixsq.nii.ac.jp/records/174612554e4cd4-c893-4d23-83d7-e27024bd9546
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL16159005.pdf (491.0 kB)
|
Copyright (c) 2016 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2016-09-16 | |||||||
| タイトル | ||||||||
| タイトル | 単純<i>b</i>-マッチングのDulmage-Mendelsohn分解 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Dulmage-Mendelsohn Decomoposition for Simple b-Matchings | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 国立情報学研究所 | ||||||||
| 著者名 |
喜多, 奈々緒
× 喜多, 奈々緒
|
|||||||
| 著者名(英) |
Nanao, Kita
× Nanao, Kita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | マッチング理論においては総称して標準分解と呼ばれるいくつかの分解型構造定理が強力な道具となるが，古典的な Dulmage - Mendelsoh 分解とは 2 部グラフを対象する標準分解のひとつであり，与えられた 2 部グラフが持つ標準的な束構造を通して全ての最大 1 - マッチングとその双対最適解である最小点被覆の族の構造を記述する．これはグラフ理論的文脈のみならず，大規模疎行列による連立方程式の効率的解法など行列計算の分野への応用が報告されている他，基本分割理論の原型を与えるなど劣モジュラ関数論への貢献が知られている．一方，b - マッチングもまた古典的な概念でありこれは 1 - マッチングの代表的な一般化である．本研究ではDulmage - Mendelsohn 分解を b - マッチングを対象にするものへと一般化を与え，古典的な成果と同様，2 部グラフの半順序構造の抽出ひいて最大 b - マッチングおよび双対最適解の構造を記述する． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2016-AL-159, 号 5, p. 1-3, 発行日 2016-09-16 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 2188-8566 | |||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
