A matching algorithm based on the depth first search for the general graph

被引：0

作者：

Yu, Chengcheng ^{[1
]}

Sheng Zhonge ^{[2
]}

机构：

[1] Hainan Coll Software Technol, Dept Network Engn, Qionghai 571400, Hainan, Peoples R China

[2] Hainan Univ, Coll Informat Sci & Technol, Haikou 570228, Hainan, Peoples R China

来源：

PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON INFORMATION, ELECTRONICS AND COMPUTER | 2014年 / 59卷

关键词：

Graph matching; Matching algorithm; Priority traversal; Flowering algorithm;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper, a matching algorithm of general graph based on depth-first traversal is proposed. The algorithm does not need to shrink and expand treatment when a flower is searched. This algorithm's time complexity of search an augmenting path is equal to corresponding graph's depth-first traversal algorithm's time complexity, it is one of the most efficient algorithm. Experiments show that this algorithm can correctly handle the associated practical problems, and have the correct conclusion.

引用

页码：59 / 63

页数：5

共 10 条

[1] [Anonymous], AM MATH MONTHLY
[2] [Anonymous], LABELLING OBTAIN MAX
[3] PATHS TREES AND FLOWERS
EDMONDS, J
[J]. CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03): : 449 - &
[4] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES
EDMONDS, J
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 125 - +
[5] EFFICIENT IMPLEMENTATION OF EDMONDS ALGORITHM FOR MAXIMUM MATCHING ON GRAPHS
GABOW, HN
[J]. JOURNAL OF THE ACM, 1976, 23 (02) : 221 - 234
[6] O(/V/./E/) ALGORITHM FOR MAXIMUM MATCHING OF GRAPHS
KAMEDA, T
MUNRO, I
[J]. COMPUTING, 1974, 12 (01) : 91 - 98
[7] The Hungarian Method for the assignment problem
Kuhn, HW
[J]. NAVAL RESEARCH LOGISTICS, 2005, 52 (01) : 7 - 21
[8] Micali S., 1980, 21st Annual Symposium on Foundations of Computer Science, P17
[9] Vaidya P. M., 1988, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, P422, DOI 10.1145/62212.62253
[10] MODIFICATION OF EDMONDS MAXIMUM MATCHING ALGORITHM
WITZGALL, C
ZAHN, CT
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 91 - +

← 1 →