The Capacity Expansion Path Problem in Networks
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/156901 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832564079738224640 |
|---|---|
| author | Jianping Li Juanping Zhu |
| author_facet | Jianping Li Juanping Zhu |
| author_sort | Jianping Li |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-b795605d780e4c27b59dab7e18b6883e |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-b795605d780e4c27b59dab7e18b6883e2025-02-03T01:11:53ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/156901156901The Capacity Expansion Path Problem in NetworksJianping Li0Juanping Zhu1Department of Mathematics, Yunnan University, Kunming 650091, ChinaDepartment of Mathematics, Yunnan University, Kunming 650091, ChinaThis 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.http://dx.doi.org/10.1155/2013/156901 |
| spellingShingle | Jianping Li Juanping Zhu The Capacity Expansion Path Problem in Networks Journal of Applied Mathematics |
| title | The Capacity Expansion Path Problem in Networks |
| title_full | The Capacity Expansion Path Problem in Networks |
| title_fullStr | The Capacity Expansion Path Problem in Networks |
| title_full_unstemmed | The Capacity Expansion Path Problem in Networks |
| title_short | The Capacity Expansion Path Problem in Networks |
| title_sort | capacity expansion path problem in networks |
| url | http://dx.doi.org/10.1155/2013/156901 |
| work_keys_str_mv | AT jianpingli thecapacityexpansionpathprobleminnetworks AT juanpingzhu thecapacityexpansionpathprobleminnetworks AT jianpingli capacityexpansionpathprobleminnetworks AT juanpingzhu capacityexpansionpathprobleminnetworks |