Smart Phone and Next Generation Mobile Computing

Mobile Networking Challenges 293

In a more general sense, the topology control problem in MANET

can be characterized by a triple of the form <M, P, O>, where M

denotes the graph model (directional or unidirectional), P denotes

the desired graph property such as the k-edge connected and bounded

maximum node degree, and O represents the power minimiza-

tion objective (i.e., maximum power and total power) [27]. The

problem of minimizing the maximum power is NP-complete (A deci-

sion problem is NP-complete if and only if it is in NP and it is

NP-hard. Readers who are interested in computational complex-

ity can refer to M. Garey and D. Johnson’s book “Computers

and Intractability: A Guide to the Theory of NP-Completeness”.).

Furthermore, the problem of