Premium
Network upgrading problems
Author(s) -
Paik Doowon,
Sahni Sartaj
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260105
Subject(s) - upgrade , computer science , vertex (graph theory) , enhanced data rates for gsm evolution , time complexity , signal flow graph , telecommunications network , mathematical optimization , graph , algorithm , theoretical computer science , mathematics , computer network , artificial intelligence , electrical engineering , engineering , operating system
Graphs with weights and delays associated with their edges and/or vertices are often used to model communication and signal flow networks. Network performance can be improved by upgrading the network vertices. Such an upgrade reduces the edge/vertex delays and comes at a cost. We study different formulations of this network performance improvement problem and show that these are NP ‐hard. We then consider one of the formulations and develop polynomial time algorithms for some special cases and pseudopolynomial time algorithms for others.