LOCATING A POINT OF MINIMUM VARIANCE ON TRIANGULAR GRAPHS

In this paper the convexity of the variance measure on triangular graphs is established, and an expression for the point that minimizes the variance on an edge is given. A transformation 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.

• Availability:
  • Find a library where document is available. Order URL: https://www.library.northwestern.edu/find-borrow-request/requests-interlibrary-loan/lending-institutions.html
• Authors:
  • Kincaid, R K
  • Maimon, O Z
• Publication Date: 1989-8

Media Info

• Features: Figures; References;
• Pagination: p. 216-219
• Serial:
  • Transportation Science
  • Volume: 23
  • Issue Number: 3
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Algorithms; Facilities; Location; Minimization; Trees (Mathematics); Variance
• Old TRIS Terms: Triangular graphs
• Subject Areas: Highways; Planning and Forecasting; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00488572
• Record Type: Publication
• Files: TRIS
• Created Date: Oct 31 1989 12:00AM