Optimal Bridge, Twin Bridges and Beyond: Inserting Edges into a Road Network to Minimize the Constrained Diameters
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914777279758336 |
|---|---|
| author | Feng, Zhidan Fernau, Henning Zhu, Binhai |
| author_facet | Feng, Zhidan Fernau, Henning Zhu, Binhai |
| contents | Given a road network modelled as a planar straight-line graph $G=(V,E)$ with $|V|=n$, let $(u,v)\in V\times V$, the shortest path (distance) between $u,v$ is denoted as $δ_G(u,v)$. Let $δ(G)=\max_{(u,v)}δ_G(u,v)$, for $(u,v)\in V\times V$, which is called the diameter of $G$. Given a disconnected road network modelled as two disjoint trees $T_1$ and $T_2$, this paper first aims at inserting one and two edges (bridges) between them to minimize the (constrained) diameter $δ(T_1\cup T_2\cup I_j)$ going through the inserted edges, where $I_j, j=1,2$, is the set of inserted edges with $|I_1|=1$ and $|I_2|=2$. The corresponding problems are called the {\em optimal bridge} and {\em twin bridges} problems. Since when more than one edge are inserted between two trees the resulting graph is becoming more complex, for the general network $G$ we consider the problem of inserting a minimum of $k$ edges such that the shortest distances between a set of $m$ pairs $P=\{(u_i,v_i)\mid u_i,v_i\in V, i\in [m]\}$, $δ_G(u_i,v_i)$'s, are all decreased.
The main results of this paper are summarized as follows:
(1) We show that the optimal bridge problem can be solved in $O(n^2)$ time and that a variation of it has a near-quadratic lower bound unless SETH fails. The proof also implies that the famous 3-SUM problem does have a near-quadratic lower bound for large integers, e.g., each of the $n$ input integers has $Ω(\log n)$ decimal digits. We then give a simple factor-2 $O(n\log n)$ time approximation algorithm for the optimal bridge problem.
(2) We present an $O(n^4)$ time algorithm to solve the twin bridges problem, exploiting some new property not in the optimal bridge problem.
(3) For the general problem of inserting $k$ edges to reduce the (graph) distances between $m$ given pairs, we show that the problem is NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19164 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Bridge, Twin Bridges and Beyond: Inserting Edges into a Road Network to Minimize the Constrained Diameters Feng, Zhidan Fernau, Henning Zhu, Binhai Computational Geometry 68 F.2.2 Given a road network modelled as a planar straight-line graph $G=(V,E)$ with $|V|=n$, let $(u,v)\in V\times V$, the shortest path (distance) between $u,v$ is denoted as $δ_G(u,v)$. Let $δ(G)=\max_{(u,v)}δ_G(u,v)$, for $(u,v)\in V\times V$, which is called the diameter of $G$. Given a disconnected road network modelled as two disjoint trees $T_1$ and $T_2$, this paper first aims at inserting one and two edges (bridges) between them to minimize the (constrained) diameter $δ(T_1\cup T_2\cup I_j)$ going through the inserted edges, where $I_j, j=1,2$, is the set of inserted edges with $|I_1|=1$ and $|I_2|=2$. The corresponding problems are called the {\em optimal bridge} and {\em twin bridges} problems. Since when more than one edge are inserted between two trees the resulting graph is becoming more complex, for the general network $G$ we consider the problem of inserting a minimum of $k$ edges such that the shortest distances between a set of $m$ pairs $P=\{(u_i,v_i)\mid u_i,v_i\in V, i\in [m]\}$, $δ_G(u_i,v_i)$'s, are all decreased. The main results of this paper are summarized as follows: (1) We show that the optimal bridge problem can be solved in $O(n^2)$ time and that a variation of it has a near-quadratic lower bound unless SETH fails. The proof also implies that the famous 3-SUM problem does have a near-quadratic lower bound for large integers, e.g., each of the $n$ input integers has $Ω(\log n)$ decimal digits. We then give a simple factor-2 $O(n\log n)$ time approximation algorithm for the optimal bridge problem. (2) We present an $O(n^4)$ time algorithm to solve the twin bridges problem, exploiting some new property not in the optimal bridge problem. (3) For the general problem of inserting $k$ edges to reduce the (graph) distances between $m$ given pairs, we show that the problem is NP-complete. |
| title | Optimal Bridge, Twin Bridges and Beyond: Inserting Edges into a Road Network to Minimize the Constrained Diameters |
| topic | Computational Geometry 68 F.2.2 |
| url | https://arxiv.org/abs/2404.19164 |