1
$\begingroup$

My problem is to find places to put k number of shortcut edges with weight 0 to minimize maximum distance in grid graph where all edges are weighted 1! I found a related topic to my question Minimizing distance on a graph by adding shortcuts but similar to Christopher I don't understand many mathematical concepts.

I've tried to analyze Paper that Christopher found but still don't know how could I implement this to my problem! Trying to be more specified let's look at grid graph:

Grid graph

I want to add k shortcut edges to minimize maximum distance. Example:

Grid graph with shortcuts

So the question in what is the which nodes to connect, and how to prove that this is the best solution!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

It's not hard to bound the new distance to within a constant factor, as a function of $k$. If you add $k$ shortcut edges to an $n\times n$ grid, the number of points within distance $d$ of an endpoint of a shortcut will be $O(kd^2)$, so unless $d$ is big enough to make this $n^2$ there will be some points farther from any shortcut endpoint than this. Therefore, the distance will remain at least proportional to $n/\sqrt k$, no matter where you put the shortcuts.

On the other hand, by spacing the shortcuts evenly throughout the grid, you can ensure that every point can reach at least one shortcut within distance proportional to $n/\sqrt k$. And by connecting the shortcuts themselves into a star topology (a tree with one interior node and $k$ leaves) you can make the distances between any two shortcuts negligible. So the best distance you can achieve is both upper-bounded and lower-bounded proportional to $n/\sqrt k$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for response, but could you please explain where does 2k(2d+1)^2 and n/sqrt(k) comes from? Also d is distance from random node to nearest shortcut yes? Sorry for my probobly dummy questions but I'm just a begginer! $\endgroup$
    – Kubinho10
    Commented Dec 29, 2017 at 23:38
  • $\begingroup$ I simplified that part to $O(kd^2)$. It's just counting how many points are within that distance on a grid. $d$ can be any number you want it to be, and the $O(kd^2)$ bound on how many points are within that distance of shortcut endpoints will remain valid. $\endgroup$
    – David Eppstein
    Commented Dec 30, 2017 at 4:45
  • $\begingroup$ Okey it's true that the best possible will always be n/sqrt(k),but still I don't know which nodes shuld i connect, because it does matter which nodes are connected. $\endgroup$
    – Kubinho10
    Commented Dec 30, 2017 at 11:14
  • $\begingroup$ And I would be gratefull if you could explain what big O is doing here:] $\endgroup$
    – Kubinho10
    Commented Dec 30, 2017 at 11:38
  • $\begingroup$ Re which nodes to connect: "by spacing the shortcuts evenly throughout the grid" $\endgroup$
    – David Eppstein
    Commented Dec 30, 2017 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .