Approximating the max-edge-coloring problem
DOI10.1016/J.TCS.2010.04.031zbMATH Open1196.68321OpenAlexW2082958680MaRDI QIDQ986540FDOQ986540
G. 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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- Batch processing with interval graph compatibilities between tasks
- Edge and total coloring of interval graphs
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
- On the max-weight edge coloring problem
- Approximating the Max Edge-Coloring Problem
- Regular Graphs of High Degree are 1-Factorizable
- On the Max Coloring Problem
- Title not available (Why is that?)
- Batch Coloring Flat Graphs and Thin
- Automata, Languages and Programming
- Time slot scheduling of compatible jobs
- Scheduling in switching networks with set-up delays
- On approximating a scheduling problem
- Some results concerning the complexity of restricted colorings of graphs
- Restrictions and preassignments in preemptive open shop scheduling
- On the Maximum Edge Coloring Problem
Cited In (12)
- An exponential time 2-approximation algorithm for bandwidth
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- An asymptotic approximation scheme for multigraph edge coloring
- On the max coloring problem
- Title not available (Why is that?)
- Approximation and Hardness Results for the Maximum Edge q-coloring Problem
- Title not available (Why is that?)
- Bounded max-colorings of graphs
- Approximation and hardness results for the maximum edge \(q\)-coloring problem
- On the Maximum Edge Coloring Problem
- Optimal edge coloring of large graphs
- Improved approximation algorithms for the max edge-coloring problem
Recommendations
This page was built for publication: Approximating the max-edge-coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986540)
