On the max-weight edge coloring problem

DOI10.1007/s10878-009-9223-zzbMath1207.05199OpenAlexW2053823962MaRDI QIDQ613668

Ioannis Milis, Giorgio Lucarelli, 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

polynomial algorithmsapproximation algorithmsweighted edge coloring

Mathematics Subject Classification ID

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

Related Items (4)

The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ On the max coloring problem ⋮ Approximating the max-edge-coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Weighted coloring: further complexity and approximability results
• On the complexity of decomposing matrices arising in satellite communication
• Scheduling a batching machine
• Scheduling in switching networks with set-up delays
• Batch processing with interval graph compatibilities between tasks
• The NP-Completeness of Edge-Coloring
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Algorithms and Computation
• Automata, Languages and Programming
• On approximating a scheduling problem
• Edge and total coloring of interval graphs

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