{"ID":2831893,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.08111","arxiv_id":"2512.08111","title":"The Bichromatic Two-Center Problem on Graphs","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.08111","url_pdf":"https://arxiv.org/pdf/2512.08111v1","authors":"[\"Qi Sun\",\"Jingru Zhang\"]","published":"2025-12-08T23:27:32Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}