Parallel algorithms for finding the most vital edge with respect to minimum spanning tree

DOI10.1016/0167-8191(92)90061-BzbMATH Open0795.68087OpenAlexW2034581303MaRDI QIDQ1201944FDOQ1201944

Authors: Lih-Hsing Hsu, Chu-Tao Wu, Pengfei Wang 

Publication date: 17 January 1993

Published in: Parallel Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-8191(92)90061-b

Recommendations

• Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
• Parallel algorithm for finding the most vital edge in weighted graphs
• scientific article; zbMATH DE number 24457
• Efficient algorithms for finding the \(k\) most vital edges for the minimum spanning tree problem
• scientific article; zbMATH DE number 1556480
• A Parallel Algorithm for Computing Minimum Spanning Trees
• Parallel Algorithms for Minimum Spanning Tree Problem
• Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
• An optimal parallel algorithm for minimum spanning trees in planar graphs
• An efficient parallel algorithm for multiple edge updates of minimum spanning trees on sparse graphs

zbMATH Keywords

minimum spanning treeweighted graphcost-optimal parallel algorithmsvital edge

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cited In (6)

• Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
• Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
• The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• NC algorithms for the Single Most Vital Edge problem with respect to shortest paths

This page was built for publication: Parallel algorithms for finding the most vital edge with respect to minimum spanning tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1201944)