The most vital edges of matching in a bipartite graph | Zendy

Hung ChunNan | Zendy; Hsu LihHsing | Zendy; Sung TingYi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research