Channel assignment via fast zeta transform

We show an O⁎(n(ℓ+1))O⁎((ℓ+1)n)-time algorithm for the channel assignment problem, where ℓ   is the maximum edge weight. This improves on the previous O⁎(n(ℓ+2))O⁎((ℓ+2)n)-time algorithm by Král (2005) [1], as well as algorithms for important special cases, like L(2,1)L(2,1)-labeling. For the latter problem, our algorithm works in O⁎(n3)O⁎(3n) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion–exclusion principle.

► Exact algorithm for the channel assignment problem running in O⁎(n(ℓ+1))O⁎((ℓ+1)n) time. ► This improves the previously best O⁎(n(ℓ+2))O⁎((ℓ+2)n) time algorithm by Král. ► An O⁎(n3)O⁎(3n) time algorithm for the L(2,1)L(2,1)-labeling problem.