Approximating the max-edge-coloring problem
From MaRDI portal
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)- Optimal edge coloring of large graphs
- On the Complexity of the Max-Edge-Coloring Problem with Its Variants
- An exponential time 2-approximation algorithm for bandwidth
- Approximation Algorithms for Maximum Edge Coloring Problem
- Approximation and Hardness Results for the Maximum Edge q-coloring Problem
- scientific article; zbMATH DE number 1947051 (Why is no real title available?)
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- On the max coloring problem
- On the Maximum Edge Coloring Problem
- Approximating the max edge-coloring problem
- Approximation and hardness results for the maximum edge \(q\)-coloring problem
- Improved approximation algorithms for the max edge-coloring problem
- scientific article; zbMATH DE number 6469191 (Why is no real title available?)
- An asymptotic approximation scheme for multigraph edge coloring
- Improved approximation algorithms for the max-edge coloring problem
- On the max-weight edge coloring problem
- Bounded max-colorings of graphs
- Progress (and lack thereof) for graph coloring approximation problems
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)
