Premium
Efficient algorithms for a simple network design problem
Author(s) -
Nakano Shinichi,
Uehara Ryuhei,
Uno Takeaki
Publication year - 2013
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.21500
Subject(s) - reachability , minimum weight , node (physics) , simple (philosophy) , enhanced data rates for gsm evolution , network planning and design , algorithm , mathematics , computer science , combinatorics , tree (set theory) , weighted network , efficient algorithm , discrete mathematics , complex network , computer network , telecommunications , philosophy , structural engineering , epistemology , engineering
We consider the following simple network design problem. The input consists of n weighted nodes, and the output is an edge‐weighted connected network such that the total weight of the edges incident to a node is at least the given weight of the node. We aim to design the cheapest connected network; that is, the reachability of the network should be guaranteed, and the network is better if its total weight is less. In this article, we first show an efficient algorithm that produces an optimal network with minimum weight. The algorithm runs in linear time, and the resulting network contains at most n edges, where n is the number of nodes. To construct a connected network, at least n ‐ 1 edges are required. However, the algorithm sometimes outputs n edges. Next, we aim to minimize not only the weight but also the number of edges. That is, for given n weighted nodes, we aim to design a cheapest tree. Then, the problem becomes \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{N}\mathcal{P}\end{align*} \end{document} ‐complete. We also propose efficient approximation algorithms for constructing a cheapest tree. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013