🚀 go-pugleaf

This talk would interest some CS students as well.
samir

---------- Forwarded message ----------
Date: Mon,  8 Sep 2008 11:43:22 -0400 (EDT)
From: Sirin Nitinawarat <nitinawa@umd.edu>
To: adrian@glue.umd.edu, abarg@glue.umd.edu, srin@cs.umd.edu, damianos@jhu.edu,
     hyongla@glue.umd.edu, jkatz@cs.umd.edu, samir@cs.umd.edu,
     prakash@glue.umd.edu, khudanpur@jhu.edu, ulukus@glue.umd.edu,
     jornjustesen@starpower.net, nmartins@isr.umd.edu, lvaczlav@umd.edu,
     poorvi@gwu.edu, edowaks@umd.edu, baras@umd.edu, krishna@umd.edu,
     armand@umd.edu, minwu@umd.edu, marcus@umd.edu, akomaee@glue.umd.edu,
     alkan@glue.umd.edu, borbash@ieee.org, nagarajp@umd.edu,
     aduggan@alum.mit.edu, ashwins@umd.edu, ppurka@umd.edu, nitinawa@wam.umd.edu,
     srikanth@umd.edu, pshang@gwu.edu, eswaran@umd.edu, wkang@glue.umd.edu,
     sshafiee@glue.umd.edu, bshrader@umd.edu, kseddik@umd.edu, asalah@umd.edu,
     ravit@umd.edu, mnsefat@umd.edu, vijay@cds.caltech.edu, gelareh@glue.umd.edu,
     ksayrafian@yahoo.com, ashok.veeraraghavan@gmail.com, bhatv@umd.edu,
     apantel@glue.umd.edu, sina_919@yahoo.com, gad@umd.edu, arya@umd.edu,
     mjmirbagheri@gmail.com, kirans@umd.edu, wuyl@umd.edu, bassily@umd.edu,
     liruonan@umd.edu, davood.shamsi@gmail.com, mingyliu@umd.edu,
     john_kuykendall@ctdata.com, vishwa@umd.edu, waseemmalik@gmail.com,
     byrong@umd.edu, suresh.purini@gmail.com, kmitra@umiacs.umd.edu,
     tyagi@umd.edu, nshroff@umd.edu, ksjain@umd.edu, shalabh@umd.edu,
     posulliv@umd.edu, kh_macdonald@yahoo.com, dhahn@umd.edu, adeoras@jhu.edu,
     ppakoo@gmail.com, ajsnyder1@yahoo.com, varna@umd.edu, tekinay@njit.edu,
     asadek@qualcomm.com, ankurs@umd.edu, marcos@umd.edu, ersen@umd.edu,
     oyagan@umd.edu, vijaymahad@gmail.com, houdavid@umd.edu,
     menkulasi@econ.umd.edu, gcstein@gmail.com
Subject: Information and Coding Theory Research Seminars: Thursday, September 11

Dear all,

Professor Barg and Professor Narayan welcome you to the first talk of our Fall 2008 seminars on this Thursday.

Here is information about the talk.


TOPIC: Coloring Rooted Subtrees of a Bidirected Tree
VENUE: 2168 AVW
DATE/TIME: Thursday, September 11, 5:00pm
SPEAKER: Anuj Rawat (UMD)

ABSTRACT: A bidirected tree is a directed graph obtained from a tree by replacing all the edges of the tree by pairs of directed anti-parallel edges. The degree (depth) of a bidirected tree is defined to be the degree (depth) of the tree from which it is constructed.

We study the problem of assigning colors to a given set of rooted subtrees of a given bidirected tree such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The objective is to minimize the total number of colors used in the coloring. The problem is NP hard even in the restricted cases when (i) the degree of the bidirected tree is restricted to being 2, and (ii) the depth of the bidirected tree is restricted to being 2. This problem is motivated by the problem of assigning wavelengths to multicast traffic requests in all-optical tree networks.

We present a greedy coloring scheme for the case when the degree of the bidirected tree is restricted to 3 and prove that it is a 5/2-approximation algorithm. We then present another, simpler coloring scheme and prove that it is an approximation algorithm for the problem with approximation ratio 10/3, 3 and 2 for the cases when the degree of the bidirected tree is restricted to 4, 3 and 2, respectively.


Thank you.

Sirin Nitinawarat