An inverse model for the least uniform spanning tree problems

Author

Long-Shu, Wu ; Qin, Wang ; Cheng, Qiao

Author_Institution

Coll. of Sci., China Jiliang Univ., Hangzhou, China

fYear

2009

fDate

25-28 July 2009

Firstpage

1949

Lastpage

1952

Abstract

In this paper, we consider an inverse model for the least uniform spanning tree (ILUS) problems. Let T be a spanning tree of a network G. Define the degree of balance of T as the difference between the maximum and the minimum weight of the edges in T. (ILUS) problem can be described as: how to change the weight vector w of G under a given budget constraint so that the maximum degree of balance of the spanning trees of G is minimized. After discussing some characteristics of (ILUS) problem, we show that this problem can be solved efficiently by strongly polynomial algorithm.

Keywords

inverse problems; polynomials; trees (mathematics); graph theory; inverse model; least uniform spanning tree problem; polynomial algorithm; Computational complexity; Computer science; Computer science education; Cost function; Educational institutions; Inverse problems; Investments; Mathematical model; Mathematics; Polynomials; Computational complexity; Inverse optimization; Least uniform spanning tree; Strongly polynomial algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science & Education, 2009. ICCSE '09. 4th International Conference on

Conference_Location

Nanning

Print_ISBN

978-1-4244-3520-3

Electronic_ISBN

978-1-4244-3521-0

Type

conf

DOI

10.1109/ICCSE.2009.5228220

Filename

5228220