ABSTRACT

We address the problems of link scheduling (LSP) and broadcast scheduling (BSP) in radio networks. We reduce LSP to BSP to graph coloring to independent set to a Hopfield network. All local minima of the Hopfield network represent feasible solutions of the original problem (LSP or BSP). We show that steepest descent (SD) dynamics on the Hopfield network, from different initial states, emulates various graph coloring heuristics. We report on preliminary experiments on BSP using SD dynamics on the Hopfield network.