Improved approximation algorithms for the max-edge coloring problem

DOI10.1007/978-3-642-19754-3_21MaRDI QIDQ2999347zbMATH OpenOpenAlexFDO

Authors G. Lucarelli, Ioannis Milis

Publication date 12 May 2011

Published in Theory and Practice of Algorithms in (Computer) Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-19754-3_21

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Improved approximation algorithms for the max edge-coloring problem
• Approximating the max edge-coloring problem
• Approximating the max-edge-coloring problem
• On the Maximum Edge Coloring Problem
• On the max-weight edge coloring problem

Cited in

(12)

• Improved Inapproximability Results for Maximum k-Colorable Subgraph
• On the Complexity of the Max-Edge-Coloring Problem with Its Variants
• Approximation and Hardness Results for the Maximum Edge q-coloring Problem
• On the Maximum Edge Coloring Problem
• Approximating the max edge-coloring problem
• Approximation and hardness results for the maximum edge \(q\)-coloring problem
• Improved approximation algorithms for the max edge-coloring problem
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Improving the performance guarantee for approximate graph coloring
• On the max-weight edge coloring problem
• Approximate constrained bipartite edge coloring
• Approximating the max-edge-coloring problem

This page was built for publication: Improved approximation algorithms for the max-edge coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2999347)