<p>When the costs are all equal, you are looking for the fewest number of edges to bring your graph to being of at most diameter $k$. This is the <strong>graph diameter augmentation problem</strong>. You are looking for the edge-weighted version, which I believe has been studied as well.</p>

<p>There are a number of versions of diameter augmentation out there: some that fix or bound the amount of bridge you can build and the task is the bring the diameter down to as small as possible. Or, your version, you have some $K$ in mind and you want to find the cheapest amount of bridges in order to acheive that $K$.</p>

<p>Naming of these problems is non-standard or inconsistent in the literature, but searching for 'graph diameter augmentation' will get you on your way.</p>

CC BY-SA 3.0
2016-11-16T16:46:33.180Z
Thanks, finding a starting point is always the hardest part, especially because this is not my primary field. For anyone else who happens upon this, you should add the term "graph" to the "diameter augmentation" search, otherwise you end up getting lots of results about breast augmentation.
Erotemic
CC BY-SA 3.0
2016-11-16T22:49:20.570Z
I will edit the answer to 'graph diameter augmentation'
JimN
CC BY-SA 3.0
2016-11-15T18:47:34.207Z
2016-11-16T22:49:38.097Z
2016-11-16T22:49:38.097Z
JimN
<p>I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known. </p>

<p>The intuition for the problem is I have two islands and a set of possible locations I can build bridges between those islands. I want to determine a minimum cost set of bridges to build such that it takes a short amount of time (no longer than $K$ hours) to travel from any point on the first island to any point on the second island.  </p>

<p>To put this into a graph context: We are given two connected components $A$ and $B$ and a set of edges $\{e\}$ with cost $c_e$ required to add them to the graph. I want to find the minimum cost set of edges that connects $A$ and $B$ such that the maximum unweighted distance between any any two nodes between the components is at most $K$.</p>

<p>More precisely:  </p>

<p>Let $x_e = 1$ if we choose to add edge $e$ and $0$ otherwise</p>

<p>Let $G' = A \cup B \cup \{e \mid x_e = 1\}$ be the graph augmented with the edges that we added.</p>

<p>Let $dist(G, u, v)$ be the length of the shorted path between $u$ and $v$ in graph $G$.</p>

<p>minimize $\sum_{e} x_e c_e$ such that</p>

<p>$ dist(G', u, v) &lt; K\quad \forall u, v \in A \times B$</p>

CC BY-SA 3.0
2016-11-16T15:22:58.030Z
Check the paper of Dodis and Khanna http://dl.acm.org/citation.cfm?id=301447. I am sure there is follow up work which you can trace via citations etc.
Chandra Chekuri
<graph-theory><graph-algorithms><optimization><linear-programming><integer-programming>
Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K
Erotemic
# Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

(Asked by: username_0 on 2016-11-10)

I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known.

The intuition for the problem is I have two islands and a set of possible locations I can build bridges between those islands. I want to determine a minimum cost set of bridges to build such that it takes a short amount of time (no longer than $K$ hours) to travel from any point on the first island to any point on the second island.

To put this into a graph context: We are given two connected components $A$ and $B$ and a set of edges $\{e\}$ with cost $c\_e$ required to add them to the graph. I want to find the minimum cost set of edges that connects $A$ and $B$ such that the maximum unweighted distance between any any two nodes between the components is at most $K$.

More precisely:

Let $x\_e = 1$ if we choose to add edge $e$ and $0$ otherwise

Let $G' = A \cup B \cup \{e \mid x\_e = 1\}$ be the graph augmented with the edges that we added.

Let $dist(G, u, v)$ be the length of the shorted path between $u$ and $v$ in graph $G$.

minimize $\sum\_{e} x\_e c\_e$ such that

$ dist(G', u, v) < K\quad \forall u, v \in A \times B$

**Tags:** graph-theory, graph-algorithms, optimization, linear-programming, integer-programming
> **Comments:**
> **username_1**: Check the paper of Dodis and Khanna http://dl.acm.org/citation.cfm?id=301447. I am sure there is follow up work which you can trace via citations etc.  

---

## 1 answers

### Answer by username_2 on 2016-11-15. Score: 1 | Accepted answer

When the costs are all equal, you are looking for the fewest number of edges to bring your graph to being of at most diameter $k$. This is the **graph diameter augmentation problem**. You are looking for the edge-weighted version, which I believe has been studied as well.

There are a number of versions of diameter augmentation out there: some that fix or bound the amount of bridge you can build and the task is the bring the diameter down to as small as possible. Or, your version, you have some $K$ in mind and you want to find the cheapest amount of bridges in order to acheive that $K$.

Naming of these problems is non-standard or inconsistent in the literature, but searching for 'graph diameter augmentation' will get you on your way.

> **Comments:**
> **username_0**: Thanks, finding a starting point is always the hardest part, especially because this is not my primary field. For anyone else who happens upon this, you should add the term "graph" to the "diameter augmentation" search, otherwise you end up getting lots of results about breast augmentation.  
> **username_2**: I will edit the answer to 'graph diameter augmentation'  

---

