跳到主要导航 跳到搜索 跳到主要内容

On Computing the Edge-Connectivity of an Uncertain Graph

  • Yuan Gao
  • , Zhongfeng Qin*
  • *此作品的通讯作者
  • Beijing Jiaotong University
  • Beihang University

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

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.

源语言英语
期刊论文编号7328258
页(从-至)981-991
页数11
期刊IEEE Transactions on Fuzzy Systems
卷24
期4
DOI
出版状态已出版 - 1 8月 2016
已对外发布是

学术指纹

探究 'On Computing the Edge-Connectivity of an Uncertain Graph' 的科研主题。它们共同构成独一无二的学术指纹。

引用此