Channel Assignment via Fast Zeta Transform
Cygan, Marek · Kowalik, Łukasz
Original · EN
We show an O*((l+1)ⁿ)-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)ⁿ)-time algorithm by Kral, as well as algorithms for important special cases, like L(2,1)-labelling. For the latter problem, our algorithm works in O*(3ⁿ) time. The progress is achieved by applying the fast zeta transform in combination with the inclusion-exclusion principle.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.