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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3654142 (Why is no real title available?)
- scientific article; zbMATH DE number 6469191 (Why is no real title available?)
- Approximating the max edge-coloring problem
- Automata, Languages and Programming
- Batch Coloring Flat Graphs and Thin
- Batch processing with interval graph compatibilities between tasks
- Edge and total coloring of interval graphs
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- On approximating a scheduling problem
- On the Max Coloring Problem
- On the Maximum Edge Coloring Problem
- On the max-weight edge coloring problem
- Regular Graphs of High Degree are 1-Factorizable
- Restrictions and preassignments in preemptive open shop scheduling
- Scheduling in switching networks with set-up delays
- Some results concerning the complexity of restricted colorings of graphs
- The NP-Completeness of Edge-Coloring
- Time slot scheduling of compatible jobs
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Weighted coloring: further complexity and approximability results
Cited in
(18)- Approximating the max edge-coloring problem
- An exponential time 2-approximation algorithm for bandwidth
- Improved approximation algorithms for the max-edge coloring problem
- On approximate graph colouring and MAX-k-CUT algorithms based on the -function
- An asymptotic approximation scheme for multigraph edge coloring
- On the max coloring problem
- scientific article; zbMATH DE number 6469191 (Why is no real title available?)
- Approximation and Hardness Results for the Maximum Edge q-coloring Problem
- scientific article; zbMATH DE number 1947051 (Why is no real title available?)
- On the Complexity of the Max-Edge-Coloring Problem with Its Variants
- Progress (and lack thereof) for graph coloring approximation problems
- Bounded max-colorings of graphs
- On the max-weight edge coloring problem
- Approximation and hardness results for the maximum edge q-coloring problem
- Approximation Algorithms for Maximum Edge Coloring Problem
- On the Maximum Edge Coloring Problem
- Optimal edge coloring of large graphs
- Improved approximation algorithms for the max edge-coloring problem
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)
