A $$\frac{5}{2}$$52-approximation algorithm for coloring rooted subtrees of a degree 3 tree

Anuj Rawat () and Mark Shayman ()
Additional contact information
Anuj Rawat: Intel Corp.
Mark Shayman: University of Maryland

Journal of Combinatorial Optimization, 2020, vol. 40, issue 1, No 6, 69-97

Abstract: Abstract A rooted tree $$\mathbf {R}$$R is a rooted subtree of a tree T if the tree obtained by replacing the directed edges of $$\mathbf {R}$$R by undirected edges is a subtree of T. We study the problem of assigning minimum number of colors to a given set of rooted subtrees $${\mathcal {R}}$$R of a given tree T such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The problem is NP hard even in the case when the degree of T is restricted to at most 3 (Erlebach and Jansen, in: Proceedings of the 30th Hawaii international conference on system sciences, p 221, 1997). We present a $$\frac{5}{2}$$52-approximation algorithm for this problem. The motivation for studying this problem stems from the problem of assigning wavelengths to multicast traffic requests in all-optical WDM tree networks.

Keywords: Approximation algorithms; Analysis of algorithms; Graph coloring; Trees; 68W25; 68W40; 68R10; 05C85; 05C15; 05C05 (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00564-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:40:y:2020:i:1:d:10.1007_s10878-020-00564-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00564-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().