Improved approximation algorithms for the max edge-coloring problem
From MaRDI portal
Publication:1944142
DOI10.1016/j.ipl.2011.05.019zbMath1260.05166OpenAlexW1544742712MaRDI QIDQ1944142
Giorgio Lucarelli, Ioannis Milis
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.05.019
Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
The assignment problem with nearly Monge arrays and incompatible partner indices, Bounded max-colorings of graphs, On the max coloring problem
Cites Work
- On the max-weight edge coloring problem
- Time slot scheduling of compatible jobs
- Approximating the max-edge-coloring problem
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- Some results concerning the complexity of restricted colorings of graphs
- Restrictions and preassignments in preemptive open shop scheduling
- Batch processing with interval graph compatibilities between tasks
- Max-Coloring Paths: Tight Bounds and Extensions
- An algorithmic proof of Tutte's f-factor theorem
- Automata, Languages and Programming
