Graph radio coloring concepts

Authors

  • R. Kalfakakou Aristotle University of Thessaloniki, Faculty of Engineering Thessaloniki, Greece
  • G. Nikolakopoulou Aristotle University of Thessaloniki, Faculty of Engineering Thessaloniki, Greece
  • E. Savvidou Aristotle University of Thessaloniki, Faculty of Engineering Thessaloniki, Greece
  • M. Tsouros Aristotle University of Thessaloniki, Faculty of Engineering Thessaloniki, Greece

DOI:

https://doi.org/10.2298/YJOR0302207K

Keywords:

graph, radio coloring, algorithm, channel assignment

Abstract

The evolution of the telecommunication technology, such as mobile telecommunication equipment, radio, television, teleconferencing, etc necessitated the existence of numerously broadcast channels. However the corresponding frequencies may interfere for reason of distance, geographical or atmospherical structure or for a variety of other factors. In the present paper we give the definition of the graph radio coloring concept which is a graph coloring generalization. We also introduce radio coloring invariants which are of a great practical importance to problems regarding the allocation of diverse frequencies in order to avoid interference occurrences between channel transmissions. A heuristic algorithm that finds approximate values of the radio chromatic number and radio chromatic cost of a given graph is developed and the result of a computational experiment of the proposed algorithm is given. .

References

Michaels, J.G., and Rosen, K.H., Applications of Discrete Mathematics, McGraw-Hill Inc, 1991.

Harary, F., Private communication.

Harary, F., Graph Theory, Addison-Wesley, Reading MA, 1969.

Christofides, N., Graph Theory, an Algorithmic Approach, Academic Press, New York, 1975.

Cameron, and Wu, Y., "A frequency assignment algorithm based on a minimum residual difficulty heuristic", Proc. IEEE Int.Symp. EMC 79 (CH 13839 EMC), 1979, 350-354.

Hale, W.K., "Frequency assignment: Theory and applications", Proceedings of the IEEE, 69 (12) (1980).

Aardal, K., Hurkens, A., Lenstra, J.K., and Tourine, S.R., "Algorithms for frequency assignment problems", CWI Quarterly, 9 (1996) 1-9.

Murphey, R.A., Pardalos, P.M., and Resende, M.G.C., "Frequency assignment problems", in: Handbook of Combinatorial Optimization, Kluwer Academic Press, 1999.

Savvidou, E., "Algorithm for graph coloring, radiocoloring and predefined coloring separation", Dpt of Appl. Informatic, Univ. of Macedonia, Thessaloniki, 2001.

Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, San Francisco, 1979.

Downloads

Published

2003-09-01

Issue

Vol. 13 No. 2 (2003)

Section

Research Articles

License

Copyright (c) 2003 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.