The Capacity Expansion Path Problem in Networks
Joint Authors
Source
Journal of Applied Mathematics
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-4, 4 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-07-16
Country of Publication
Egypt
No. of Pages
4
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Li, Jianping& Zhu, Juanping. 2013. The Capacity Expansion Path Problem in Networks. Journal of Applied Mathematics،Vol. 2013, no. 2013, pp.1-4.
https://search.emarefa.net/detail/BIM-450319
Modern Language Association (MLA)
Li, Jianping& Zhu, Juanping. The Capacity Expansion Path Problem in Networks. Journal of Applied Mathematics No. 2013 (2013), pp.1-4.
https://search.emarefa.net/detail/BIM-450319
American Medical Association (AMA)
Li, Jianping& Zhu, Juanping. The Capacity Expansion Path Problem in Networks. Journal of Applied Mathematics. 2013. Vol. 2013, no. 2013, pp.1-4.
https://search.emarefa.net/detail/BIM-450319
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-450319