Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.08111 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911309431308288 |
|---|---|
| author | Sun, Qi Zhang, Jingru |
| author_facet | Sun, Qi Zhang, Jingru |
| contents | In this paper, we study the (weighted) bichromatic two-center problem on graphs. The input consists of a graph $G$ of $n$ (weighted) vertices and $m$ edges, and a set $\mathcal{P}$ of pairs of distinct vertices, where no vertex appears in more than one pair. The problem aims to find two points (i.e., centers) on $G$ by assigning vertices of each pair to different centers so as to minimize the maximum (weighted) distance of vertices to their assigned centers (so that the graph can be bi-colored with this goal). To the best of our knowledge, this problem has not been studied on graphs, including tree graphs. In this paper, we propose an $O(m^2n\log n\log mn)$ algorithm for solving the problem on an undirected graph provided with the distance matrix, an $O(n\log n)$-time algorithm for the problem on trees, and a linear-time approach for the unweighted tree version. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_08111 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Bichromatic Two-Center Problem on Graphs Sun, Qi Zhang, Jingru Data Structures and Algorithms In this paper, we study the (weighted) bichromatic two-center problem on graphs. The input consists of a graph $G$ of $n$ (weighted) vertices and $m$ edges, and a set $\mathcal{P}$ of pairs of distinct vertices, where no vertex appears in more than one pair. The problem aims to find two points (i.e., centers) on $G$ by assigning vertices of each pair to different centers so as to minimize the maximum (weighted) distance of vertices to their assigned centers (so that the graph can be bi-colored with this goal). To the best of our knowledge, this problem has not been studied on graphs, including tree graphs. In this paper, we propose an $O(m^2n\log n\log mn)$ algorithm for solving the problem on an undirected graph provided with the distance matrix, an $O(n\log n)$-time algorithm for the problem on trees, and a linear-time approach for the unweighted tree version. |
| title | The Bichromatic Two-Center Problem on Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.08111 |