Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2408.13688 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Table des matières:
- 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.