DocumentCode
2854391
Title
The Constrained Min-Max Spanning Tree Problem
Author
Wang Qin ; Qiao Cheng
Author_Institution
Dept. of Math., China Jiliang Univ., Hangzhou, China
fYear
2009
fDate
19-20 Dec. 2009
Firstpage
1
Lastpage
3
Abstract
In this paper, we consider the constrained min-max spanning tree problem (CMMSTP), which is to and a spanning tree of a network under an additional linear constraint such that the maximum edge weight of this spanning tree is minimum among all the spanning trees. After discussing some characteristics of (CMMSTP), we show that this problem can be solved efficiently by strongly polynomial algorithm. Some extentions of (CMMSTP) are also discussed in brief.
Keywords
computational complexity; minimax techniques; polynomials; trees (mathematics); combinatorial optimization; computational complexity; constrained min-max spanning tree problem; linear constraint; polynomial algorithm; Computational complexity; Constraint optimization; Costs; Investments; Mathematics; Polynomials; Roads; Telecommunication traffic; Tree graphs;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Engineering and Computer Science, 2009. ICIECS 2009. International Conference on
Conference_Location
Wuhan
Print_ISBN
978-1-4244-4994-1
Type
conf
DOI
10.1109/ICIECS.2009.5365603
Filename
5365603
Link To Document