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

DOI10.1007/s10878-020-00564-6zbMath1445.05041arXiv1805.07867OpenAlexW3016149321MaRDI QIDQ2185817

Anuj Rawat, Mark A. Shayman

Publication date: 5 June 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.07867

zbMATH Keywords

graph coloringanalysis of algorithmstreesapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on optical routing on trees
• The edge intersection graphs of paths in a tree
• Weakly triangulated graphs
• Decomposition by clique separators
• Constant tolerance intersection graphs of subtrees of a tree
• Incidence matrices and interval graphs
• Efficient routing in all-optical networks
• Improved algorithms for weakly chordal graphs
• On the $1.1$ Edge-Coloring of Multigraphs
• Finding Intersection Models of Weakly Chordal Graphs
• The NP-Completeness of Edge-Coloring
• Constrained bipartite edge coloring with applications to wavelength routing
• Efficient wavelength routing on directed fiber trees
• STACS 2004
• Approximation Algorithms for Path Coloring in Trees
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The complexity of path coloring and call scheduling

This page was built for publication: A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree