Show simple item record

Coloring Rooted Subtrees on a Bounded Degree Host Tree

dc.contributor.authorRawat, Anuj
dc.contributor.authorShayman, Mark
dc.contributor.authorLa, Richard J.
dc.contributor.authorMarcus, Steven I.
dc.date.accessioned2008-06-16T14:21:04Z
dc.date.available2008-06-16T14:21:04Z
dc.date.issued2007
dc.identifier.urihttp://hdl.handle.net/1903/8003
dc.description.abstractWe consider a rooted tree R to be a rooted subtree of a given tree T if the tree obtained by replacing the directed arcs of R by undirected edges is a subtree of T. In this work, we study the problem of assigning colors to a given set of rooted subtrees of a given host 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 case when the degree of the host tree is restricted to 3. 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 host 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 host tree is restricted to 4, 3, and 2, respectively.en
dc.format.extent539807 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen
dc.relation.ispartofseriesTR 2008-10en
dc.subjectapproximation algorithmsen
dc.subjectanalysis of algorithmsen
dc.subjectvertex coloringen
dc.subjectgraph algorithmsen
dc.subjectrooted treesen
dc.titleColoring Rooted Subtrees on a Bounded Degree Host Treeen
dc.typeArticleen
dc.relation.isAvailableAtInstitute for Systems Researchen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record