Modified and Improved Algorithm for Finding a Median Path with a Specific Length ( ℓ ) for a Tree Network

Abdallah Aboutahoun, Salem Mahdi (), Mahmoud El-Alem and Mohamed ALrashidi
Additional contact information
Abdallah Aboutahoun: Department of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, Egypt
Salem Mahdi: Department of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, Egypt
Mahmoud El-Alem: Department of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, Egypt
Mohamed ALrashidi: Department of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, Egypt

Mathematics, 2023, vol. 11, issue 16, 1-25

Abstract: The median path problem (min-sum criterion) is a common problem in graph theory and tree networks. This problem is open to study because its applications are growing and extending in different fields, such as providing insight for decision-makers when selecting the optimal location for non-emergency services, including railroad lines, highways, pipelines, and transit routes. Also, the min-sum criterion can deal with several networks in different applications. The location problem has traditionally been concerned with the optimal location of a single-point facility at either a vertex or along an edge in a network. Recently, numerous investigators have investigated this classic problem and have studied the location of many facilities, such as paths, trees, and cycles. The concept of the median, which measures the centrality of a vertex in a graph, is extended to the paths in a graph. In this paper, we consider the problem of locating path-shaped facilities on a tree network. A new modified and improved algorithm for finding a median single path facility of a specified length in a tree network is proposed. The median criterion for optimality considers the sum of the distances from all vertices of the tree to the path facility. This problem under the median criterion is called the ℓ -core problem. The distance between any two vertices in the tree is equal to the length of the unique path connecting them. This location problem usually has applications in distributed database systems, pipelines, the design of public transportation routes, and communication networks.

Keywords: core; facility location; median; central diameter of a tree; tree network (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/16/3585/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/16/3585/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:16:p:3585-:d:1220414

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().