Scholarlink

<p>This paper investigates stochastic spanning tree problems with incomplete edge weight information. In order to propose efficient algorithms for addressing these issues, we adopt sublinear expectation theory, as formulated by Shige Peng. Firstly, the concept of ambiguous minimum spanning tree under minimum expectation (minimally expected AMST) is introduced. Additionally, we present an equivalent definition, a mathematical programming model, and a path optimality condition for it. Meanwhile, we demonstrate that this problem can be transformed into a related classical minimum spanning tree problem and provide an algorithm to find such a spanning tree. Furthermore, concepts of ambiguous <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> </InlineEquation>-minimum spanning tree under lower distribution (lower distributed <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> </InlineEquation>-AMST) and maximally reliable <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(w^*\)</EquationSource> </InlineEquation>-ambiguous spanning tree (maximally reliable <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(w^*\)</EquationSource> </InlineEquation>-AST) are described. Specifically, a mathematical programming model and an equivalent definition of lower distributed <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> </InlineEquation>-AMST are presented. Moreover, we also investigate the relationship between these two spanning trees and give some algorithms to find them. Finally, some numerical examples are discussed to illustrate these three types of minimum stochastic spanning tree problems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Stochastic spanning tree problems with incomplete edge weight information

  • 期刊论文

  • 发表日期：

    2025年10月23日

查看全文
  • Deguo Yang,
  • Feng Hu

摘要

This paper investigates stochastic spanning tree problems with incomplete edge weight information. In order to propose efficient algorithms for addressing these issues, we adopt sublinear expectation theory, as formulated by Shige Peng. Firstly, the concept of ambiguous minimum spanning tree under minimum expectation (minimally expected AMST) is introduced. Additionally, we present an equivalent definition, a mathematical programming model, and a path optimality condition for it. Meanwhile, we demonstrate that this problem can be transformed into a related classical minimum spanning tree problem and provide an algorithm to find such a spanning tree. Furthermore, concepts of ambiguous \(\alpha \) -minimum spanning tree under lower distribution (lower distributed \(\alpha \) -AMST) and maximally reliable \(w^*\) -ambiguous spanning tree (maximally reliable \(w^*\) -AST) are described. Specifically, a mathematical programming model and an equivalent definition of lower distributed \(\alpha \) -AMST are presented. Moreover, we also investigate the relationship between these two spanning trees and give some algorithms to find them. Finally, some numerical examples are discussed to illustrate these three types of minimum stochastic spanning tree problems.