The most vital edges with respect to the number of spanning trees in two-terminal series-parallel graphs | Zendy

RongHong Jan | Zendy; Lih-Hsing Hsu | Zendy; Yueh-Ying Lee | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The most vital edges with respect to the number of spanning trees in two-terminal series-parallel graphs

Author(s) -

RongHong Jan,

Lih-Hsing Hsu,

Yueh-Ying Lee

Publication year - 1992

Publication title -

bit numerical mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.904

H-Index - 59

eISSN - 1572-9125

pISSN - 0006-3835

DOI - 10.1007/bf02074877

Subject(s) - combinatorics , terminal (telecommunication) , spanning tree , series (stratigraphy) , mathematics , set (abstract data type) , enhanced data rates for gsm evolution , discrete mathematics , computer science , artificial intelligence , biology , telecommunications , paleontology , programming language

A setE′ ofk edges in a multigraphG=(V,E) is said to be ak most vital edge set (k-MVE set) if these edges being removed fromG, the resultant graphG′=(V,E −E′) has minimum number of spanning trees. The problem of finding ak-MVE set for two-terminal series-parallel graphs is considered in this paper. We present anO (|E|) time algorithm for the casek=1, and anO(|V|k+|E|) time algorithm for arbitraryk.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research