Finding the most vital edge with respect to minimum spanning tree in weighted graphs

DOI10.1016/0020-0190(91)90028-GzbMath0749.68043WikidataQ127939718 ScholiaQ127939718MaRDI QIDQ1183410

Rong-Hong Jan, Maw-Sheng Chern, Lih-Hsing Hsu, Yu-Che Lee, Chun-Nan Hung

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

minimum spanning tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items

A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges, Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, Integer Programming Formulations for Minimum Spanning Tree Interdiction, Parametric matroid interdiction, The tree longest detour problem in a biconnected graph., NC algorithms for the Single Most Vital Edge problem with respect to shortest paths, Element perturbation problems of optimum spanning trees with two-parameter objectives, Super edge magic graceful graphs, Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, The most vital edges in the minimum spanning tree problem, Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs, Globally and locally minimal weight spanning tree networks, Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\), Efficient algorithms for finding the most vital edge of a minimum spanning tree, Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Most vital links and nodes in weighted networks
• Finding the most vital arcs in a network
• Efficiency of a Good But Not Linear Set Union Algorithm