Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
An orientation of an undirected graph is a choice of direction for each of its edges. An orientation is called ideal with respect to a given set of pairs of vertices if it does not increase the shortest-path distances between the members of any of the pairs. A polynomial-time algorithm is given for constructing an ideal orientation with respect to two given pairs and any positive edge-lengths, or else recognizing that no such orientation exists. Moreover, we show that this problem is in the class NC. For a general number of pairs the problem is proven NP-complete even with unit edge-lengths. © 1989.
Tong Zhang, G.H. Golub, et al.
Linear Algebra and Its Applications
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Charles Micchelli
Journal of Approximation Theory