Approximation algorithm for maximum edge coloring

DOI10.1016/J.TCS.2008.10.035zbMath1162.68043OpenAlexW2010526719MaRDI QIDQ1007243

Hanpin Wang, Li'ang Zhang, Wangsen Feng

Publication date: 20 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.035

zbMATH Keywords

approximation algorithmwireless mesh networksmaximum edge coloring

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

On \(\mathrm{M}_f\)-edge colorings of graphs ⋮ Improved approximation for maximum edge colouring problem ⋮ Approximation and hardness results for the maximum edge \(q\)-coloring problem ⋮ New bounds on the anti-Ramsey numbers of star graphs via maximum edge \(q\)-coloring ⋮ Complexity of Computing the Anti-Ramsey Numbers for Paths.

Cites Work

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Almost all k-colorable graphs are easy to color
• The NP-Completeness of Edge-Coloring
• The Complexity of Near-Optimal Graph Coloring
• Matching, Euler tours and the Chinese postman
• The Factors of Graphs
• A Short Proof of the Factor Theorem for Finite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithm for maximum edge coloring