# On the k-connected minimum energy problem

*by Dr Christina Burt*

*Institution:*MASCOS, The University of Melbourne

*Date: Thu 2nd July 2009*

*Time: 2:00 PM*

*Location: Room 213, Richard Berry Bldg, The University of Melbourne*

*Abstract*: We study k-connected networks, which are graphs which are

fault-resistant in the sense that they remain connected if up to k

nodes drop out. We wish to solve the minimum-energy problem on such

networks, which determines the range of each node such that the sum of

the ranges over the network is minimised, while still keeping the

k-connected constraint. In this talk, we construct an integer program

which solves this problem using network flow concepts, and investigate

the use of valid inequalities and heuristics that will allow us to

consider large networks.

A possible application of this work is in wireless ad hoc mobile phone

networks, where phones transmit directly

to each other without an intermediate tower, but possibly with

intermediate phones. The phones then form a graph structure for which

the minimum-energy k-connected problem is especially relevant.

*For More Information:* contact: Kerem Akartunali. email: kerema@unimelb.edu.au