WEKO3
アイテム
制限付き<i>t</i>-マッチング問題に対する制約充足的アプローチ
https://ipsj.ixsq.nii.ac.jp/records/228947
https://ipsj.ixsq.nii.ac.jp/records/22894710c59543-75ca-48cf-8f33-b9aa1c81d7e4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL23195027.pdf (1.1 MB)
2025年11月9日からダウンロード可能です。
|
Copyright (c) 2023 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-11-09 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 制限付き<i>t</i>-マッチング問題に対する制約充足的アプローチ | |||||||||||
| タイトル | ||||||||||||
| 言語 | en | |||||||||||
| タイトル | Constraint Satisfaction Approach to Restricted <i>t</i>-Matching Problems | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 京都大学 | ||||||||||||
| 著者所属 | ||||||||||||
| 法政大学 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Kyoto University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Kyoto University | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Hosei University | ||||||||||||
| 著者名 |
岩政, 勇仁
× 岩政, 勇仁
× 小林, 佑輔
× 高澤, 兼二郎
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | グラフ G=(V, E) の枝部分集合M⊆Eがt-マッチングであるとは，G の各頂点に接続しているMの枝が高々 t 本であることをいう．また G のある部分グラフの族 K に対して t-マッチング M が K-free であるとは，任意の K∈K に対して E(K)⊆M，すなわち，M が K に属する任意の部分グラフ K を包含しないことをいう．本研究で，我々は・Kに含まれる部分グラフが全て t-正則完全多部グラフであり，それらが互いに枝素であるときもしくは・K に含まれる部分グラフが全て t-正則完全多部グラフであり，G の最大次数が高々 2t-1 のとき最大サイズの K-free t-マッチング M⊆E を求める問題が多項式時間で解けること示した． | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2023-AL-195, 号 27, p. 1-4, 発行日 2023-11-09 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
