Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-08-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/16/3585 |
| _version_ | 1797584005060624384 |
|---|---|
| author | Abdallah Aboutahoun Salem Mahdi Mahmoud El-Alem Mohamed ALrashidi |
| author_facet | Abdallah Aboutahoun Salem Mahdi Mahmoud El-Alem Mohamed ALrashidi |
| author_sort | Abdallah Aboutahoun |
| collection | DOAJ |
| description | 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 <i>ℓ</i>-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. |
| first_indexed | 2024-03-10T23:46:07Z |
| format | Article |
| id | doaj.art-ff2dd656baff47ce8bff094ba33631f6 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T23:46:07Z |
| publishDate | 2023-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-ff2dd656baff47ce8bff094ba33631f62023-11-19T02:04:11ZengMDPI AGMathematics2227-73902023-08-011116358510.3390/math11163585Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree NetworkAbdallah Aboutahoun0Salem Mahdi1Mahmoud El-Alem2Mohamed ALrashidi3Department of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, EgyptDepartment of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, EgyptDepartment of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, EgyptDepartment of Mathematics & Computer Science, Faculty of Science, Alexandria University, Alexandria 21544, EgyptThe 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 <i>ℓ</i>-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.https://www.mdpi.com/2227-7390/11/16/3585corefacility locationmediancentral diameter of a treetree network |
| spellingShingle | Abdallah Aboutahoun Salem Mahdi Mahmoud El-Alem Mohamed ALrashidi Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network Mathematics core facility location median central diameter of a tree tree network |
| title | Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network |
| title_full | Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network |
| title_fullStr | Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network |
| title_full_unstemmed | Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network |
| title_short | Modified and Improved Algorithm for Finding a Median Path with a Specific Length (<i>ℓ</i>) for a Tree Network |
| title_sort | modified and improved algorithm for finding a median path with a specific length i l i for a tree network |
| topic | core facility location median central diameter of a tree tree network |
| url | https://www.mdpi.com/2227-7390/11/16/3585 |
| work_keys_str_mv | AT abdallahaboutahoun modifiedandimprovedalgorithmforfindingamedianpathwithaspecificlengthiliforatreenetwork AT salemmahdi modifiedandimprovedalgorithmforfindingamedianpathwithaspecificlengthiliforatreenetwork AT mahmoudelalem modifiedandimprovedalgorithmforfindingamedianpathwithaspecificlengthiliforatreenetwork AT mohamedalrashidi modifiedandimprovedalgorithmforfindingamedianpathwithaspecificlengthiliforatreenetwork |