Minimizing the total weighted pairwise connection time in network construction problems
From MaRDI portal
Publication:6365627
DOI10.1016/J.ORL.2021.10.005arXiv2104.09312MaRDI QIDQ6365627
Publication date: 19 April 2021
Abstract: 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.
Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)
This page was built for publication: Minimizing the total weighted pairwise connection time in network construction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6365627)
