Title :
The Constrained Min-Max Spanning Tree Problem
Author :
Wang Qin ; Qiao Cheng
Author_Institution :
Dept. of Math., China Jiliang Univ., Hangzhou, China
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;
Conference_Titel :
Information Engineering and Computer Science, 2009. ICIECS 2009. International Conference on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4244-4994-1
DOI :
10.1109/ICIECS.2009.5365603
