• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Gathering information in a graph

Beaudou L., Grappe R., Hahn G.

Suppose each vertex in a graph G has a unit of information and that all the units must be collected at a vertex u in G. Assuming that a vertex can receive (from its neighbours) an unlimited number of units at each discrete moment but can only send one at a time, find the shortest collection time, col u(G), needed to collect all the information at u and an optimal protocol that achieves this. We derive lower and upper bounds for the problem, give a polynomial time algorithm in the general case, and a linear time algorithm for hypercubes.