It is required to find an optimal order of constructing the edges of a network so as to minimize the sum of the weighted connection times of relevant pairs of vertices. Construction can be performed anytime anywhere i...
详细信息
It is required to find an optimal order of constructing the edges of a network so as to minimize the sum of the weighted connection times of relevant pairs of vertices. Construction can be performed anytime anywhere in the network, with a fixed overall construction speed. The problem is strongly NP-hard even on stars. We present polynomial algorithms for the problem on trees with a fixed number of leaves, and on general networks with a fixed number of relevant pairs. (C) 2021 Elsevier B.V. All rights reserved.
暂无评论