Locating a point of minimum variance on triangular graphs. (English) Zbl 0682.90034

Kincaid, Rex K.; Maimon, Oded Z.

Transp. Sci. 23, No. 3, 216-219 (1989).

Summary: The convexity of the variance measure for triangular graphs is established, and an expression for the point that minimizes the variance on an edge is given. A transformaton of triangular graphs into trees provides an efficient means to implement these properties via a postorder search of a tree. The result is a linear time algorithm that determines a point of minimum variance for any triangular graph whose edge lengths satisfy the triangle inequality.

MSC:

90B05	Inventory, storage, reservoirs
90C35	Programming involving graphs or networks

Keywords:

location theory on networks; variance measure for triangular graphs; linear time algorithm