Graph Coloring Algorithms for Assignment Problems in Radio Networks.
F.Comellas , J. Ozón
Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya
pp. 49-56 of Applications of Neural Networks to Telecommunications;
Edited by: J. Alspector, R. Goodman, T.X. Brown.
Lawrence Erlbaum Associates, Publishers.
Hillsdale, New Jersey, 1995.
ISBN 0-8058-2084-1
Assignment problems in radio networks, like the channel assignment,
may be solved by graph coloring algorithms. In this paper we
compare the performance of several recent techniques on a simple
coloring problem: the search for a bipartite subgraph with the
maximum number of edges of a given graph. The algorithms considered
are a neural network, a genetic algorithm, simulated annealing and
two heuristics. The results show that one heuristic, a new
proposed multiagent system, and the standard simulated annealing
technique are faster outperforming the algorithms in the literature.
We also show how the algorithms may be easily
adapted to deal with the $k$-coloring of a graph
and can therefore be used for solving
assignment problems in telecommunications.
Load:
