CODEWITHSUNDEEP
algorithmgraph-theory
suraj
suraj

Reputation: 492

Graph Theory Algorithm

The given problem is

Given a forest with n vertices, add edges to make it into a tree with minimal diameter. I tried many approaches but none of them passed system test cases.Please suggest some algorithm to solve this problem.

This is the link of the editorial ncpc.idi.ntnu.no/ncpc2015/ncpc2015slides.pdf The problem name is Adjoin the Networks. I am not able to understand the solution provided in the editorial

Update:

https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013

This link provides the best explanation for the solution mentioned in the editorial

Upvotes: 0

Views: 183

Answers (1)

blazs
blazs

Reputation: 4845

The eccentricity of a vertex v, denoted ecc(v), is defined as ecc(v):=max_u d(u,v), i.e. as the distance to a most distant vertex in the graph. A center of a graphG is any vertex v for which ecc(v)=min_v max_u d(u,v), i.e. a center is a vertex that minimizes the eccentricity.

If you merge two trees (from different connected components), T1 and T2, by putting an edge between their centers c1 and c2, you get a tree T with diam T = max(diam T1, diam T2, 1+rad(T1)+rad(T2)).

The correctness of the approach below should be evident from these properties.

Here's one idea for the algorithm, off the top of my head:

  • let T1, T2, ..., Tk be the trees comprising the forest.
  • compute a center vertex ci for each of the trees Ti.
  • connect components by putting edges between centers in an intelligent way.

Of course, the problem is now how to cleverly solve the last bullet. Intuitively I'd suggest you connect the treest with the largest diameters first (and then update the diameter of the new tree and compute a center of the new tree). Perhaps something like this:

while the priority queue contains more than one tree do

  • let T1 and T2 be the trees with the largest diameters; let c1 and c2 be their centers;
  • connect c1 and c2 to form a new tree T;
  • compute a new center c of T, compute diam T and put T back into priority queue (which can be a max-heap that uses diameter as the key).

done

Update. I'm not sure whether to join largest-diameter trees first or the other way around (i.e. smallest-diameter trees first). But it's now very easy to do a sketch of a proof (once you figure out which way to go) that this is the right way to go.

Update. The math certainly goes through if you connect largest first (as suggested in the PDF).

Upvotes: 1

Related Questions