On distribution function of the diameter in uncertain graph

Yuan Gao; Lixing Yang; Shukai Li; Samarjit Kar

doi:10.1016/j.ins.2014.10.048

On distribution function of the diameter in uncertain graph

Yuan Gao^*, Lixing Yang, Shukai Li, Samarjit Kar

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

59 Citations (Scopus)

Abstract

In uncertain graphs, the existence of some edges is not predetermined. The diameter of an uncertain graph is essentially an uncertain variable, which indicates the suitability for investigation of its distribution function. The main focus of this paper is to propose an algorithm to determine the distribution function of the diameter of an uncertain graph. We first discuss the characteristics of the uncertain diameter, and the distribution function is derived. An efficient algorithm is designed based on Floyd's algorithm. Further, some numerical examples are illustrated to show the efficiency and application of the algorithm.

Original language	English
Pages (from-to)	61-74
Number of pages	14
Journal	Information Sciences
Volume	296
Issue number	1
DOIs	https://doi.org/10.1016/j.ins.2014.10.048
Publication status	Published - 2015
Externally published	Yes

Keywords

Distribution function
Floyd's algorithm
Graph theory
Uncertain graph
Uncertainty modeling

Access to Document

10.1016/j.ins.2014.10.048

Cite this

@article{cac63ba0d6f04e23889e487f5f1164b1,

title = "On distribution function of the diameter in uncertain graph",

abstract = "In uncertain graphs, the existence of some edges is not predetermined. The diameter of an uncertain graph is essentially an uncertain variable, which indicates the suitability for investigation of its distribution function. The main focus of this paper is to propose an algorithm to determine the distribution function of the diameter of an uncertain graph. We first discuss the characteristics of the uncertain diameter, and the distribution function is derived. An efficient algorithm is designed based on Floyd's algorithm. Further, some numerical examples are illustrated to show the efficiency and application of the algorithm.",

keywords = "Distribution function, Floyd's algorithm, Graph theory, Uncertain graph, Uncertainty modeling",

author = "Yuan Gao and Lixing Yang and Shukai Li and Samarjit Kar",

year = "2015",

doi = "10.1016/j.ins.2014.10.048",

language = "English",

volume = "296",

pages = "61--74",

journal = "Information Sciences",

issn = "0020-0255",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - On distribution function of the diameter in uncertain graph

AU - Gao, Yuan

AU - Yang, Lixing

AU - Li, Shukai

AU - Kar, Samarjit

PY - 2015

Y1 - 2015

N2 - In uncertain graphs, the existence of some edges is not predetermined. The diameter of an uncertain graph is essentially an uncertain variable, which indicates the suitability for investigation of its distribution function. The main focus of this paper is to propose an algorithm to determine the distribution function of the diameter of an uncertain graph. We first discuss the characteristics of the uncertain diameter, and the distribution function is derived. An efficient algorithm is designed based on Floyd's algorithm. Further, some numerical examples are illustrated to show the efficiency and application of the algorithm.

AB - In uncertain graphs, the existence of some edges is not predetermined. The diameter of an uncertain graph is essentially an uncertain variable, which indicates the suitability for investigation of its distribution function. The main focus of this paper is to propose an algorithm to determine the distribution function of the diameter of an uncertain graph. We first discuss the characteristics of the uncertain diameter, and the distribution function is derived. An efficient algorithm is designed based on Floyd's algorithm. Further, some numerical examples are illustrated to show the efficiency and application of the algorithm.

KW - Distribution function

KW - Floyd's algorithm

KW - Graph theory

KW - Uncertain graph

KW - Uncertainty modeling

UR - http://www.scopus.com/inward/record.url?scp=84961291904&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2014.10.048

DO - 10.1016/j.ins.2014.10.048

M3 - Article

AN - SCOPUS:84961291904

SN - 0020-0255

VL - 296

SP - 61

EP - 74

JO - Information Sciences

JF - Information Sciences

IS - 1

ER -

On distribution function of the diameter in uncertain graph

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this