Generation of all permutation and combination of Matchings in a Bipartite graph and its applications
This paper discusses an approach to generate all permutations and combinations of valid matching edges, valid pass -through edges and un -matched edges of a Bipartite graph (B -graph). Matchings would range from no -match to perfect - match. B -graph is represented as matrix where rows and columns represent two disjoint sets of vertex and its values represent the edges. It involves 3 stages of operation to get all sets of valid matched edges, pass -through edges and un - matched edges of a B -graph. In first stage, the rows and columns of a perfect -match B -graph matrix are swapped to get all permutations. In second stage, each of those B -graph matrix are superimposed over set of binary -matrix (generated by incrementing integers) and AND logical operation is performed on the matrix values to create all combinations of the B -graph. In third stage, the invalid B -graphs are eliminated by checking for invalid -pass -through edges. If pass - through edges are not required, then third stage can be eliminated. Generating all permutations and combinations of B -graphs aids as an input to validate various Matching algorithms and also to represent Redundancy models of High Availability platforms.
bipartite graph matching problem maximum matching B -graph permutations combination
Saran Krishnaswamy
Motorola India Private LimitedHyderabad, India
国际会议
成都
英文
1-4
2010-08-20（万方平台首次上网日期，不代表论文的发表时间）