Volume 10 Number 1 (Jan. 2015)
Home > Archive > 2015 > Volume 10 Number 1 (Jan. 2015) >
JCP 2015 Vol.10(1): 45-56 ISSN: 1796-203X
doi: 10.17706/jcp.10.1.45-56

Reliability Evaluation of the Minimum Spanning Tree on Uncertain Graph

Jie Tang1, Yuansheng Liu1, Zhonghua Wen2
1Ministry of Education Key Laboratory of Intelligent Computing and Information Processing, College of Information Engineering, Xiangtan University, Xiangtan 411105, Hunan, China.
2Department of Computer & Communication, Hunan Institute of Engineering, Xiangtan 411104, Hunan, China.


Abstract—Minimum spanning tree is a minimum-cost spanning tree connecting the whole network, but it couldn't be directly obtained on uncertain graph. In this paper, we define the reliability as the existence probability of all minimum spanning trees and present an algorithm for evaluating reliability of the minimum spanning tree on uncertain graph. The time complexity of the algorithm is O(Nmn), where n, m and N stand for the number of vertices, edges and minimum spanning trees, respectively. Because this algorithm spends more time finding minimum spanning tree, we propose an improved algorithm whose time complexity is O(Nm). The improved algorithm uses disjoint set data structure so that the average time complexity on finding a new minimum spanning tree is O(m/n). The two algorithms are analyzed in detail and the experiment results agree with theoretical analysis.

Index Terms—Implicated graph, Minimum spanning tree, Uncertain graph.

[PDF]

Cite: Jie Tang, Yuansheng Liu, Zhonghua Wen, "Reliability Evaluation of the Minimum Spanning Tree on Uncertain Graph," Journal of Computers vol. 10, no. 1, pp. 45-56, 2015.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>