標題: | THE MOST VITAL EDGES OF MATCHING IN A BIPARTITE GRAPH |
作者: | HUNG, CN HSU, LH SUNG, TY 資訊工程學系 Department of Computer Science |
公開日期: | 1-七月-1993 |
摘要: | Let G = (VE) be an undirected graph having an edge weight w(e) greater-than-or-equal-to 0 for each e is-an-element-of 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 0(n3) algorithm to obtain the most vital edges. |
URI: | http://dx.doi.org/10.1002/net.3230230413 http://hdl.handle.net/11536/2966 |
ISSN: | 0028-3045 |
DOI: | 10.1002/net.3230230413 |
期刊: | NETWORKS |
Volume: | 23 |
Issue: | 4 |
起始頁: | 309 |
結束頁: | 313 |
顯示於類別: | 期刊論文 |