The capacity expansion path problem in networks
type: Item
instance of: scholarly article
title: The capacity expansion path problem in networks
zbMATH Open document ID: 1271.90017
DOI: 10.1155/2013/156901
author: Jianping Li
author: Juanping Zhu
published in: Journal of Applied Mathematics
publication date: 2013-09-09T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90B18
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6206758
Wikidata QID: Q59001873
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/156901
OpenAlex ID: W1963694282
cites work: Improving Minimum Cost Spanning Trees by Upgrading Nodes
cites work: A class of bottleneck expansion problems
cites work: On the bottleneck capacity expansion problems on networks
cites work: Incremental Network Optimization: Theory and Algorithms
cites work: Q4739657
cites work: Approximation Schemes for the Restricted Shortest Path Problem
cites work: Q4198056
cites work: An improved FPTAS for Restricted Shortest Path.
cites work: On a routing problem
cites work: Q3056948
description: scientific article; zbMATH DE number 6206758