Premium
The most vital edges of matching in a bipartite graph
Author(s) -
Hung ChunNan,
Hsu LihHsing,
Sung TingYi
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230413
Subject(s) - bipartite graph , combinatorics , matching (statistics) , mathematics , graph , enhanced data rates for gsm evolution , 3 dimensional matching , edge transitive graph , blossom algorithm , discrete mathematics , algorithm , computer science , line graph , graph power , artificial intelligence , statistics
Let G = (V,E) be an undirected graph having an edge weight w e ≥ 0 for each e ϵ E . An edge is called a most vital edge (with respect to weighted matching) if its removal from G results in the largest decrease in the total weight of the maximum weighted matching. In this paper, we study the most vital edges of matching in a weighted bipartite graph. We present an O ( n 3 ) algorithm to obtain the most vital edges. © 1993 by John Wiley & Sons, Inc.