Journal of Applied Mathematics
Volume 2013 (2013), Article ID 156901, 4 pages
Research Article

The Capacity Expansion Path Problem in Networks

Department of Mathematics, Yunnan University, Kunming 650091, China

Received 8 February 2013; Revised 1 June 2013; Accepted 25 June 2013

Academic Editor: Yuri Sotskov

Copyright © 2013 Jianping Li and Juanping Zhu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This paper considers the general capacity expansion path problem (GCEP) for the telecommunication operators. We investigate the polynomial equivalence between the GCEP problem and the constrained shortest path problem (CSP) and present a pseudopolynomial algorithm for the GCEP problem, no matter the graph is acyclic or not. Furthermore, we investigate two special versions of the GCEP problem. For the minimum number arc capacity expansion path problem (MN-CEP), we give a strongly polynomial algorithm based on the dynamic programming. For the minimum-cost capacity expansion shortest path problem (MCESP), we give a strongly polynomial algorithm by constructing a shortest paths network.