Inapproximability and approximability of maximal tree routing and coloring

Xujin Chen (), Xiaodong Hu () and Tianping Shuai ()
Additional contact information
Xujin Chen: Chinese Academy of Sciences
Xiaodong Hu: Chinese Academy of Sciences
Tianping Shuai: Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2006, vol. 11, issue 2, No 8, 219-229

Abstract: Abstract Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability of this problem and prove Ω(g 1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds.

Keywords: multicast routing; coloring; maximum independent set (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-006-7135-8 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:11:y:2006:i:2:d:10.1007_s10878-006-7135-8

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

DOI: 10.1007/s10878-006-7135-8

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 ().