Approximation algorithm for maximum edge coloring

DOI10.1016/J.TCS.2008.10.035MaRDI QIDQ1007243zbMATH OpenOpenAlexFDO

Authors Wangsen Feng, Li'ang Zhang, Hanpin Wang

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

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

Recommendations

• Approximation Algorithms for Maximum Edge Coloring Problem
• The min-max edge \(q\)-coloring problem
• The min-max edge \(q\)-coloring problem
• scientific article; zbMATH DE number 1947051
• scientific article; zbMATH DE number 3889546

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• A Short Proof of the Factor Theorem for Finite Graphs
• Almost all k-colorable graphs are easy to color
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Matching, Euler tours and the Chinese postman
• The Complexity of Near-Optimal Graph Coloring
• The Factors of Graphs
• The NP-Completeness of Edge-Coloring

Cited in

(17)

• On the parameterized complexity of the maximum edge 2-coloring problem
• The min-max edge \(q\)-coloring problem
• The min-max edge \(q\)-coloring problem
• Complexity of Computing the Anti-Ramsey Numbers for Paths.
• Approximating maximum edge 2-coloring by normalizing graphs
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks
• Progress (and lack thereof) for graph coloring approximation problems
• On \(\mathrm{M}_f\)-edge colorings of graphs
• Improved approximation for maximum edge colouring problem
• Efficient algorithms for the edge-cover coloring problem
• Heuristic algorithms for the min-max edge 2-coloring problem
• New bounds on the anti-Ramsey numbers of star graphs via maximum edge \(q\)-coloring
• Approximation and hardness results for the maximum edge q-coloring problem
• Approximation Algorithms for Maximum Edge Coloring Problem
• Optimal edge coloring of large graphs

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

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