############################################################
                    Seminar Announcement

            School of Computer Science, CECS
             The Australian National University
############################################################

Date:  Thursday, 02 April 2009
Time:  4:00 pm to 5:00 pm
Venue: Room N101, CSIT Building [108]


Speaker: Jaroslav Opatrny, Concordia University, Montreal

Title:   Local Algorithms for position-aware Unit Disk Graphs

Abstract:
   A distributed graph algorithm is called k-local for a
   constant k, if at any time during the computation, the
   algorithm at node n uses only information about the graph
   within a k-hop neighborhood of the node.  Thus, a propagation
   of information is not allowed in a local algorithm.

   We show that the knowledge of position of nodes in unit 
   disk graphs (UDG's) can be used to obtain distributed, local 
   algorithms for problems like dominating set, connected
   dominating set, vertex coloring of planar UDG graphs, 
   edge-coloring of Yao subgraphs of UDG.  The solutions given
   by these algorithms are within constant factor of optimal
   solutions and their run-time is constant. Furthermore, a 
   local change in the graph requires only a local change in
   a solution.

Biography:
   Jaroslav Opatrny is a professor in the Department of Computer
   Science and Software Engineering at Concordia University in
   Montreal.

   His research interests in models for ad-hoc and mobile
   networks can be seen at the URL:
         http://users.encs.concordia.ca/~opatrny/

URL: http://cs.anu.edu.au/lib/seminars/seminars09/dept20090402




############################################################
Seminars homepage:  http://cs.anu.edu.au/seminars/

If you like to give a seminar please contact:
                           seminars-owner [at] cs.anu.edu.au
############################################################