TY - JOUR
T1 - On Computing the Edge-Connectivity of an Uncertain Graph
AU - Gao, Yuan
AU - Qin, Zhongfeng
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - Uncertain graphs are employed to describe graph models with imprecise expert data. In uncertain graphs, due to the existence of uncertain edges, edge-connectivity is essentially an uncertain variable. Different from that in a deterministic graph, it is more suitable to investigate the possibility (uncertain measure) that an uncertain graph is $k$-edge-connected, which is the main aim of this paper. We first deduce a theoretical formula to calculate the uncertain measure, and on this basis, we then propose an algorithm, which is derived from maximum flow algorithms, to numerically calculate the uncertain measure. The proposed algorithm is also proved to be a polynomial time algorithm, and its effectiveness and efficiency are illustrated by numerical examples.
AB - Uncertain graphs are employed to describe graph models with imprecise expert data. In uncertain graphs, due to the existence of uncertain edges, edge-connectivity is essentially an uncertain variable. Different from that in a deterministic graph, it is more suitable to investigate the possibility (uncertain measure) that an uncertain graph is $k$-edge-connected, which is the main aim of this paper. We first deduce a theoretical formula to calculate the uncertain measure, and on this basis, we then propose an algorithm, which is derived from maximum flow algorithms, to numerically calculate the uncertain measure. The proposed algorithm is also proved to be a polynomial time algorithm, and its effectiveness and efficiency are illustrated by numerical examples.
KW - Edge-connectivity
KW - uncertain graph
KW - uncertain variable
KW - uncertainty modeling
UR - https://www.scopus.com/pages/publications/84981275844
U2 - 10.1109/TFUZZ.2015.2500267
DO - 10.1109/TFUZZ.2015.2500267
M3 - Article
AN - SCOPUS:84981275844
SN - 1063-6706
VL - 24
SP - 981
EP - 991
JO - IEEE Transactions on Fuzzy Systems
JF - IEEE Transactions on Fuzzy Systems
IS - 4
M1 - 7328258
ER -