あらまし
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
…ジュニア会員・学生員にお勧めの記事