Minimizing the total weighted pairwise connection time in network construction problems

DOI10.1016/J.ORL.2021.10.005MaRDI QIDQ6365627arXivFDO

Authors Igor Averbakh

Publication date 19 April 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2021.10.005

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)

arXiv classification

cs.DSmath.OC

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.

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)