Inapproximability and approximability of minimal tree routing and coloring

DOI10.1016/j.jda.2007.02.001zbMath1154.05312OpenAlexW2019026495WikidataQ60402674 ScholiaQ60402674MaRDI QIDQ935848

Xiao-Dong Hu, Xu-jin Chen, Xiao-Hua Jia

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.02.001

zbMATH Keywords

vertex coloringinapproximabilityapproximabilitytree coloringtree routingmulticast connections

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• The edge intersection graphs of paths in a tree
• Edge and vertex intersection of paths in a tree
• Decomposition by clique separators
• A fast algorithm for Steiner trees
• A still better performance guarantee for approximate graph coloring
• Zero knowledge and the chromatic number
• Routing algorithm for multicast under multi-tree model in optical networks
• Inapproximability and approximability of maximal tree routing and coloring
• Efficient routing in all-optical networks
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• On the $1.1$ Edge-Coloring of Multigraphs
• Hardness of the undirected congestion minimization problem
• Efficient algorithms for interval graphs and circular-arc graphs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• The complexity of path coloring and call scheduling
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Inapproximability and approximability of minimal tree routing and coloring