文献

J-GLOBAL ID：201602019404837940   整理番号：74A0221761

バイバータイトグラフの最大マッチングを求めるn^5/2アルゴリズム

An n^5/2 Algorithm for maximum matchings in bipartite graphs.

著者 (2件)： HOPCROFT J E ,  KARP RM
資料名： SIAM J Comput (Soc Ind Ap  (SIAM Journal on Computing (Society for Industrial and Applied Mathematics))
巻： 2  号： 4  ページ： 225-231  発行年： 1973年 
JST資料番号： D0944A  ISSN： 0097-5397  CODEN： SMJCAT  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： その各成分が1または0である行列をAとする。成分が1である二つの成分が同じ行にも列にもないとき独立であるという。成分が1である成分の集合どのどのにつの成分も独立のとき,Xは独立てであるという。ここではその元の個数が最大である独立集合Xを求める問題をバイパータイトグラフの最大マッチング問題として取扱い,Xを求めるアルゴリズムを与えた;写図3参5

シソーラス用語： アルゴリズム ,  グラフ理論
準シソーラス用語： 最大マッチング

タイトルに関連する用語 (2件)： 最大マッチング ,  アルゴリズム