Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗

DOI10.1080/00207160008804971zbMath0962.68178OpenAlexW2036440386MaRDI QIDQ4511611

Hong Shen

Publication date: 30 October 2000

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160008804971

zbMATH Keywords

fast parallel algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (2)

Parametric matroid interdiction ⋮ NC algorithms for the Single Most Vital Edge problem with respect to shortest paths

Cites Work

• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree
• Efficient algorithms for finding the most vital edge of a minimum spanning tree
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Applications of Path Compression on Balanced Trees
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗