IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v15y1981i2p98-114.html
   My bibliography  Save this article

Linear Algorithms for Finding the Jordan Center and Path Center of a Tree

Author

Listed:
  • S. Mitchell Hedetniemi

    (University of Oregon, Eugene, Oregon)

  • E. J. Cockayne

    (University of Victoria, Victoria, British Columbia)

  • S. T. Hedetniemi

    (University of Oregon, Eugene, Oregon)

Abstract

This paper contains linear algorithms for finding the Jordan center, the weighted Jordan center and the path center of a tree. All of these algorithms take advantage of an efficient data structure for representing a tree called a canonical recursive representation. As a result, the first two algorithms are different from and faster than similar algorithms in the literature. This paper also defines a new parameter of a graph called the path center, and shows that the path center of a tree T consists of a unique subpath of T .

Suggested Citation

  • S. Mitchell Hedetniemi & E. J. Cockayne & S. T. Hedetniemi, 1981. "Linear Algorithms for Finding the Jordan Center and Path Center of a Tree," Transportation Science, INFORMS, vol. 15(2), pages 98-114, May.
    • Handle: RePEc:inm:ortrsc:v:15:y:1981:i:2:p:98-114
    DOI: 10.1287/trsc.15.2.98
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.15.2.98
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.15.2.98?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mulder, H.M. & Pelsmajer, M.J. & Reid, K.B., 2006. "Generalized centrality in trees," Econometric Institute Research Papers EI 2006-16, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    2. Becker, Ronald I. & Lari, Isabella & Scozzari, Andrea, 2007. "Algorithms for central-median paths with bounded length on trees," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1208-1220, June.
    3. Mehdi Zaferanieh & Jafar Fathali, 2012. "Finding a core of a tree with pos/neg weight," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(2), pages 147-160, October.
    4. Marie Schmidt & Anita Schöbel, 2014. "Location of speed-up subnetworks," Annals of Operations Research, Springer, vol. 223(1), pages 379-401, December.
    5. Pascual Fernández & Blas Pelegrín & José Fernández, 1998. "Location of paths on trees with minimal eccentricity and superior section," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 6(2), pages 223-246, December.
    6. Mark Rozanov & Arie Tamir, 2018. "The nestedness property of location problems on the line," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(2), pages 257-282, July.
    7. Mehrdad Moshtagh & Jafar Fathali & James MacGregor Smith & Nezam Mahdavi-Amiri, 2019. "Finding an optimal core on a tree network with M/G/c/c state-dependent queues," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 89(1), pages 115-142, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:15:y:1981:i:2:p:98-114. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.