Finding the Center and Centroid of a Graph with Multiple Sources
<|reference_start|>Finding the Center and Centroid of a Graph with Multiple Sources: 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.<|reference_end|>
@article{chou2024finding,
    title={Finding the Center and Centroid of a Graph with Multiple Sources},
    author={Matthew Chou},
    journal={arXiv preprint arXiv:2408.13688},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.13688},
    primaryClass={cs.DM cs.DS cs.SI}
}