Preprocessing Techniques for the Multicast Problem in Wireless Networks

Many features of the wireless ad hoc networks (WAHNs) like resource limitation, multihop communication, dynamic topology and lack of infrastructure make them very attractive and rise many very challenging optimization problems. In this paper we consider some preprocessing techniques usually used to reduce the size and, consequently, the solution time for several combinatorial optimization problems in telecommunication networks. In particular, for the Minimum Power Multicasting problem (MPM) in WAHNs, we describe the related network and mathematical models and subsequently propose some original reduction procedures, based on the graph model representation.