Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 30
Graph domination, coloring and cliques in telecommunications
B. Balasundaram and S. Butenko
Abstract
This chapter aims to provide a detailed survey of existing graph models and algorithms for important problems that arise in different areas of wireless telecommunication. In particular, applications of graph optimization problems such as minimum dominating set, minimum vertex coloring and maximum clique in multihop wireless networks are discussed. Different forms of graph domination have been used extensively to model clustering in wireless ad hoc networks. Graph coloring problems and their variants have been used to model channel assignment and scheduling type problems in wireless networks. Cliques are used to derive bounds on chromatic number, and are used in models of traffic flow, resource allocation, interference, etc. In this chapter we survey the solution methods proposed in the literature for these problems and some recent theoretical results that are relevant to this area of research in wireless networks.
Keywords: Dominating sets, independent sets, cliques, coloring, wireless networks.