School Seminars and Colloquia

On the k-connected minimum energy problem

ORSUM Seminar

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: