FINDING THE MOST VITAL EDGE FOR GRAPH MINIMIZATION PROBLEMS ON MESHES AND HYPERCUBES
Weifa Liang, Xiaojun Shen, Qing‐Miao Hu · ANU Open Research (Australian National University) · 2000
Let G(V, E, w) be an undirected, weighted, connected simple graph. Let P be a minimization problem in G. Edge e*∈E is called the most vital edge if its removal from G maximizes the value of P in G(V, E-{e*}, w). This paper considers the most vital edge