3
$\begingroup$

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$

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Erotemic
    Commented Nov 16, 2016 at 16:46
  • $\begingroup$ I will edit the answer to 'graph diameter augmentation' $\endgroup$
    – JimN
    Commented Nov 16, 2016 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.