Approximating the max-edge-coloring problem
From MaRDI portal
Publication:986540
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
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
