目次あり
Laurence Pilard
生駒 : 奈良先端科学技術大学院大学, 2009.4
授業アーカイブ膨大な数の計算機から構成される大規模なネットワークでは， 個々の計算機に発生する故障を回避することができない． そのため，大規模なネットワークを対象としたシステムでは， 高度な故障耐性と自立適応性が必要とされる． 本講演では，高度な自律適応能力をそなえた分散アルゴリズムである 自己安定アルゴリズムに着目し，自己安定極大マッチング問題に関する 最新の研究動向について紹介する． 極大マッチング問題はグラフ理論においてよく研究されている問題であり， 最大マッチングに対するよい近似アルゴリズムが必要とされている． 自己安定マッチングアルゴリズムにおいては，現在まで， 任意のネットワークに対する1/2-近似アルゴリズム，特定のネットワークに 対する2/3-近似アルゴリズムしか提案されていない． 本講演では，任意のネットワークに対する2/3-近似アルゴリズムを紹介するとともに， 既存の自己安定マッチングアルゴリズムを高速化する手法についても説明する．
2009
電子化映像資料(1時間30分29秒)
情報科学研究科・ゼミナール講演 ; 平成21年度
講演者所属:Universite de Franche-Comte
講演日: 平成21年4月27日
講演場所: 情報科学研究科大講義室
英語 (eng)
英語 (eng)
