NC algorithms for the Single Most Vital Edge problem with respect to shortest paths

DOI10.1016/S0020-0190(96)00172-XMaRDI QIDQ673229zbMATH OpenOpenAlexFDO

Authors Sven Venema, Hong Shen, Francis Suraweera

Publication date 28 February 1997

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

Full work available at URL https://doi.org/10.1016/s0020-0190(96)00172-x

zbMATH Keywords

AlgorithmsParallel processingNC algorithms

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• A faster computation of the most vital edge of a shortest path
• Finding the k most vital edges in the minimum spanning tree problem
• The k most vital arcs in the shortest path problem
• Finding the k most vital edges with respect to minimum spanning tree

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• Efficient algorithms for finding the most vital edge of a minimum spanning tree
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
• Most vital links and nodes in weighted networks
• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree
• The k most vital arcs in the shortest path problem

Cited in

(7)

• A refined complexity analysis of finding the most vital edges for undirected shortest paths
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs
• Finding the anti-block vital edge of a shortest path between two nodes
• Finding the most vital node of a shortest path.
• The single most vital arc in the most economical path problem -- a parametric analysis
• A faster computation of the most vital edge of a shortest path

This page was built for publication: NC algorithms for the Single Most Vital Edge problem with respect to shortest paths

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