ABSTRACT
Ad hoc networks are formed by collections of nodes which communicate with each other through radio propagation. Topology control problems in such networks deal with the assignment of power values to the nodes so that the power assignment leads to a graph topology satisfying some specified properties. In such applications, it is important to minimize a specified function of the powers assigned to the nodes. Several versions of this minimization problem are NP-complete. This chapter discusses some known approximation algorithms for these problems. The focus is on approximation algorithms with proven performance guarantees.
