Approximating the max-edge-coloring problem

DOI10.1016/j.tcs.2010.04.031zbMath1196.68321OpenAlexW2082958680MaRDI QIDQ986540

Giorgio Lucarelli, Ioannis Milis, Nicolas Bourgeois, Vangelis Th. Paschos

Publication date: 11 August 2010

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

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/3868

zbMATH Keywords

complexityapproximation algorithmsmax-edge-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

An exponential time 2-approximation algorithm for bandwidth ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ Bounded max-colorings of graphs ⋮ On the max coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the max-weight edge coloring problem
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Time slot scheduling of compatible jobs
• 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
• Scheduling in switching networks with set-up delays
• Restrictions and preassignments in preemptive open shop scheduling
• Batch processing with interval graph compatibilities between tasks
• Batch Coloring Flat Graphs and Thin
• On the Maximum Edge Coloring Problem
• Approximating the Max Edge-Coloring Problem
• The NP-Completeness of Edge-Coloring
• Regular Graphs of High Degree are 1-Factorizable
• On the Max Coloring Problem
• Automata, Languages and Programming
• On approximating a scheduling problem
• Edge and total coloring of interval graphs