THE MOST VITAL EDGES OF MATCHING IN A BIPARTITE GRAPH Version 4.0

General Search Results--Full Record

Article 11 of 13

THE MOST VITAL EDGES OF MATCHING IN A BIPARTITE GRAPH
HUNG CN, HSU LH, SUNG TY
NETWORKS 23: (4) 309-313 JUL 1993

Document type: Article

Language: English

Cited References: 5

Times Cited: 6

Abstract:
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.

Addresses:
HUNG CN, NATL CHIAO TUNG UNIV, DEPT COMP & INFORMAT SCI, HSINCHU, TAIWAN.
ACAD SINICA, INST INFORMAT SCI, TAIPEI 115, TAIWAN.

Publisher:
JOHN WILEY & SONS INC, NEW YORK

IDS Number:
LH183

ISSN:
0028-3045

Article 11 of 13