Finding the most vital edge for graph minimization problems on meshes and hypercubes

Weifa Liang*, Xiaojun Shen, Qing Hu

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    5 Citations (Scopus)

    Abstract

    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 with respect to the minimum spanning tree problem and the single-source shortest path problem. An O(n) optimal algorithm for finding the most vital edge with respect to these two problems on an n×n mesh array is presented. The algorithm is simulated on an n×n×n hypercube array, and an O(log2 n) time algorithm is then obtained, which is faster than a previously known result on the same model.

    Original languageEnglish
    Pages (from-to)197-205
    Number of pages9
    JournalInternational Journal of Parallel and Distributed Systems and Networks
    Volume3
    Issue number4
    Publication statusPublished - 2000

    Fingerprint

    Dive into the research topics of 'Finding the most vital edge for graph minimization problems on meshes and hypercubes'. Together they form a unique fingerprint.

    Cite this