On the max-weight edge coloring problem

DOI10.1007/S10878-009-9223-ZMaRDI QIDQ613668zbMATH OpenOpenAlexFDO

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

Publication date 21 December 2010

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://basepub.dauphine.fr/handle/123456789/2373

zbMATH Keywords

approximation algorithmspolynomial algorithmsweighted edge coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Recommendations

• On the Maximum Edge Coloring Problem
• Approximating the max-edge-coloring problem
• Approximating the max 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
• Edge and total coloring of interval graphs
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• On approximating a scheduling problem
• On the complexity of decomposing matrices arising in satellite communication
• Scheduling a batching machine
• Scheduling in switching networks with set-up delays
• The NP-Completeness of Edge-Coloring
• Weighted coloring: further complexity and approximability results

Cited in

(14)

• Approximating the max edge-coloring problem
• Improved approximation algorithms for the max-edge coloring problem
• Algorithms and Computation
• Densities, matchings, and fractional edge-colorings
• On the max coloring problem
• Conversion of coloring algorithms into maximum weight independent set algorithms
• On a max-min problem concerning weights of edges
• On the Complexity of the Max-Edge-Coloring Problem with Its Variants
• The assignment problem with nearly Monge arrays and incompatible partner indices
• Bounded max-colorings of graphs
• On weighted bipartite edge coloring
• On the Maximum Edge Coloring Problem
• Approximating the max-edge-coloring problem
• Improved approximation algorithms for the max edge-coloring problem

This page was built for publication: On the max-weight edge coloring problem

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