Exact algorithms for Frequency Assignment: Branching versus Dynamic Programming


One thoroughly studied model of the Frequency Assignment Problem is the distance-constrained graph labeling. In particular, an L(2,1)-labeling of a graph is a labeling of its vertices by nonnegative integers such that the labels of adjacent vertices differ by at least 2, and every two vertices with a common neighbor receive different labels. This problem exhibits a remarkably different behavior than ordinary graph coloring - a linear time algorithm for trees is an open problem, and it becomes NP-complete already for graphs of tree-width 2.

Games, Puzzles, and Computation


One can frame a game or a puzzle as a decision problem: from this configuration, does the puzzle have a solution? Can Black win the game? The computational complexity of the decision problem can then be investigated. I will begin by reviewing the properties of the complexity classes I'll be discussing (NP-complete, PSPACE-complete, etc.), then briefly present several recent hardness results, including sliding-block puzzles, sliding-coin puzzles, TipOver, Rush Hour, Sokoban, hinged polygon dissections, plank puzzles, the Dyson telescope game, Amazons, and Konane.


Subscribe to RSS - Colloquium