Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2408.13688 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917757803560960 |
|---|---|
| author | Chou, Matthew |
| author_facet | Chou, Matthew |
| contents | We consider the problem of finding a "fair" meeting place when S people want to get together. Specifically, we will consider the cases where a "fair" meeting place is defined to be either 1) a node on a graph that minimizes the maximum time/distance to each person or 2) a node on a graph that minimizes the sum of times/distances to each of the sources. In graph theory, these nodes are denoted as the center and centroid of a graph respectively. In this paper, we propose a novel solution for finding the center and centroid of a graph by using a multiple source alternating Dijkstra's Algorithm. Additionally, we introduce a stopping condition that significantly saves on time complexity without compromising the accuracy of the solution. The results of this paper are a low complexity algorithm that is optimal in computing the center of S sources among N nodes and a low complexity algorithm that is close to optimal for computing the centroid of S sources among N nodes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13688 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finding the Center and Centroid of a Graph with Multiple Sources Chou, Matthew Discrete Mathematics Data Structures and Algorithms Social and Information Networks E.1.3; G.2.2; H.4.0 We consider the problem of finding a "fair" meeting place when S people want to get together. Specifically, we will consider the cases where a "fair" meeting place is defined to be either 1) a node on a graph that minimizes the maximum time/distance to each person or 2) a node on a graph that minimizes the sum of times/distances to each of the sources. In graph theory, these nodes are denoted as the center and centroid of a graph respectively. In this paper, we propose a novel solution for finding the center and centroid of a graph by using a multiple source alternating Dijkstra's Algorithm. Additionally, we introduce a stopping condition that significantly saves on time complexity without compromising the accuracy of the solution. The results of this paper are a low complexity algorithm that is optimal in computing the center of S sources among N nodes and a low complexity algorithm that is close to optimal for computing the centroid of S sources among N nodes. |
| title | Finding the Center and Centroid of a Graph with Multiple Sources |
| topic | Discrete Mathematics Data Structures and Algorithms Social and Information Networks E.1.3; G.2.2; H.4.0 |
| url | https://arxiv.org/abs/2408.13688 |