Efficient points on a network. (English) Zbl 0644.90029

Hansen, Pierre; Thisse, Jacques-François; Wendell, Richard E.

Networks 16, No. 4, 357-368 (1986).

Summary: Properties of efficient points on a network are given. They are then used to devise (i) a linear algorithm for efficient points on a tree, (ii) an O(m log n) algorithm for the set of links common to all shortest paths between two points, and (iii) a polynomial algorithm for efficient points on a general network.

MSC:

90B05	Inventory, storage, reservoirs
90C35	Programming involving graphs or networks
68Q25	Analysis of algorithms and problem complexity
05C05	Trees
90C31	Sensitivity, stability, parametric optimization

Keywords:

location; multiple objective problem; efficient points on a network; linear algorithm; tree; polynomial algorithm

References:

[1]	Chalmet, Eur. J. Opercitionol Res. 6 pp 117– (1981)
[2]	Church, Transportation Sci. 12 pp 107– (1978)
[3]	Dijkstra, Numerische Math. 1 pp 269– (1959)
[4]	and . Location on Networks. MIT Press. Cambridge. MA, 1979.
[5]	Hansen, Discrere Appl. Math. 2 pp 151– (1980)
[6]	Hansen, Ann. Discrete Math. 19 pp 201– (1984)
[7]	and , Fundamentals of Computer Algorithms. Pitman. London, 1978. · Zbl 0442.68022
[8]	Karlsson, Discrete App. Math. 6 pp 91– (1983)
[9]	On a pair of dual nonlinear programs. I. Nonlinear Programming, (Ed.), North-Holland, Amsterdam, 1967, 37–54.
[10]	Lowe, Trans protation Sci. 12 pp 298– (1978)
[11]	Lowe, Management Sci. 30 pp 1346– (1984)
[12]	A new method for checking the consistency of precedence matrices. J. Assoc. Computing Machinery (1959) 164–172. · Zbl 0086.33202
[13]	Thisse, Operations Res. 32 pp 1309– (1984)
[14]	and , Characterizing efficient points in location problems under the one-infinity norm. I. Locationcal Analysis of Public Fucilitirs, and (Eds.), North-Holland. Amsterdam. 1983, 413–429.
[15]	Wendell., AIIE Trans. 9 pp 238– (1977)