@article{natu_fang_1997, title={The point-to-point connection problem - analysis and algorithms}, volume={78}, ISSN={["0166-218X"]}, DOI={10.1016/s0166-218x(97)00010-3}, abstractNote={The point-to-point connection problem is to find a subset of arcs with minimal total cost connecting a fixed number of source-destination pairs. The problem has many variations for different applications. In this paper, we focus on a case where the source-destination pairs are prematched. We examine the structure of the problem with two source-destination pairs and provide an efficient implementation of a Dijkstra-like algorithm with time complexity O (mn + n 2 log n) . We also provide a dynamic programming algorithm with complexity O (n 11 ) for the case with three source-destination pairs. We conjecture that the same approach can be generalized for p source-destination pairs with complexity O (n 3p + 2 ) where p is fixed.}, number={1-3}, journal={DISCRETE APPLIED MATHEMATICS}, author={Natu, M and Fang, SC}, year={1997}, month={Oct}, pages={207–226} }