Inapproximability and approximability of maximal tree routing and coloring
From MaRDI portal
Publication:2498986
DOI10.1007/s10878-006-7135-8zbMath1130.90037MaRDI QIDQ2498986
Tianping Shuai, Xiao-Dong Hu, Xu-jin Chen
Publication date: 14 August 2006
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-006-7135-8
Related Items
The complexity of minimum convex coloring, Quadratic kernelization for convex recoloring of trees, Inapproximability and approximability of minimal tree routing and coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Satisfying a maximum number of pre-routed requests in all-optical rings.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Routing algorithm for multicast under multi-tree model in optical networks
- Efficient algorithms for interval graphs and circular-arc graphs
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- On Representatives of Subsets
- Algorithmic Applications in Management