The Accuracy of One Polynomial Algorithm for the Convergecast Scheduling Problem on a Square Grid with Rectangular Obstacles

We proposed a polynomial algorithm for constructing a feasible schedule and intensive numerical experiment allowed us to make a hypothesis that the algorithm constructs an optimal solution

Adil Erzin; Roman Plotnikov

2018

Scholarcy highlights

  • In the Convergecast Scheduling Problem, it is required to find in the communication graph an oriented spanning aggregation tree with a root in a base station and the arcs oriented to the root and to build a conflict-free min-length schedule for aggregating data along the arcs of the aggregation tree
  • This problem is NP-hard in general, if the communication graph is a unit square grid in each node of which there is a sensor and in which a data packet is transmitted along any edge during a one-time slot, the problem is polynomially solvable
  • We proposed a polynomial algorithm for constructing a feasible schedule and intensive numerical experiment allowed us to make a hypothesis that the algorithm constructs an optimal solution
  • We present a counterexample and prove that the proposed algorithm constructs a schedule of length at most one time round longer than the optimal schedule

Need more features? Save interactive summary cards to your Scholarcy Library.