あらまし

Open Access 話題の記事

マッチングからマトロイドパリティへ

小林 佑輔 

Vol.101 No.3pp.248-252

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集 グラフアルゴリズムの最先端

専門分野:

キーワード:
マッチンググラフアルゴリズム多項式時間アルゴリズムマトロイドパリティ

Free本文:PDF(616.4KB)

あらまし:
グラフのマッチングは,研修医の病院への割当て,学生の学校への割当て,仕事の労働者への割当てなどのモデル化を動機として,様々な分野において盛んに研究されている.本稿では,アルゴリズムに興味を持つ読者を対象とし,所望のマッチングを効率良く求めるアルゴリズムの理論について,計算機科学の視点から紹介する.まず,マッチングの概念を説明し,マッチングアルゴリズムに関する古典的な結果について述べる.そして,マトロイドパリティと呼ばれるマッチングを一般化した概念について筆者らの最新の結果とともに紹介する.

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355