Assigning Channels Via the Meet-in-the-Middle Approach

作者：Kowalik Lukasz; Socala Arkadiusz^*

来源：Algorithmica, 2016, 74(4): 1435-1452.

DOI：10.1007/s00453-015-0004-z

• CHANNEL ASSIGNMENT
• Meet-in-the-middle
• Exponential time hypothesis
• T-COLORING
• Hardness
• Exponential time

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the -bounded Channel Assignment (when the edge weights are bounded by ) running in time . This is the first algorithm which breaks the barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that Channel Assignment does not admit a -time algorithm, for a constant c independent of . We consider a similar question for Generalized -Coloring, a CSP problem that generalizes Channel Assignment. We show that Generalized -Coloring does not admit a -time algorithm, where r is the size of the instance.

• 出版日期2016-4