On the Maximum Edge Coloring Problem

DOI10.1007/978-3-540-93980-1_22MaRDI QIDQ3602848zbMATH OpenOpenAlexFDO

Authors G. Lucarelli, Ioannis Milis, Vangelis Th. Paschos

Publication date 12 February 2009

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-93980-1_22

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the max-weight edge coloring problem
• Approximating the max edge-coloring problem
• Approximating the max-edge-coloring problem
• On the Complexity of the Max-Edge-Coloring Problem with Its Variants
• Maximal edge-colorings of graphs
• scientific article; zbMATH DE number 1947051
• Maximum edge-colorings of graphs
• Approximation Algorithms for Maximum Edge Coloring Problem
• Improved approximation algorithms for the max edge-coloring problem
• Improved approximation algorithms for the max-edge coloring problem

Cites work

• scientific article; zbMATH DE number 1953087 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• Algorithms and Computation
• Automata, Languages and Programming
• Batch processing with interval graph compatibilities between tasks
• On approximating a scheduling problem
• On the complexity of decomposing matrices arising in satellite communication
• Regular Graphs of High Degree are 1-Factorizable
• Restrictions and preassignments in preemptive open shop scheduling
• Scheduling a batching machine
• Scheduling in switching networks with set-up delays
• Some results concerning the complexity of restricted colorings of graphs
• The NP-Completeness of Edge-Coloring
• Weighted coloring: further complexity and approximability results

Cited in

(13)

• On the Complexity of the Max-Edge-Coloring Problem with Its Variants
• scientific article; zbMATH DE number 2044917 (Why is no real title available?)
• A note on compact and compact circular edge-colorings of graphs
• scientific article; zbMATH DE number 6982150 (Why is no real title available?)
• Some maximum multigraphs and adge/vertex distance colourings
• Approximating the max edge-coloring problem
• Improved approximation algorithms for the max edge-coloring problem
• On weighted bipartite edge coloring
• Improved approximation algorithms for the max-edge coloring problem
• On the max-weight edge coloring problem
• Bounded max-colorings of graphs
• Generalized edge-colorings of weighted graphs
• Approximating the max-edge-coloring problem

This page was built for publication: On the Maximum Edge Coloring Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602848)