On the max-weight edge coloring problem

DOI10.1007/S10878-009-9223-ZzbMATH Open1207.05199OpenAlexW2053823962MaRDI QIDQ613668FDOQ613668

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

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

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)

Cites Work

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

Cited In (11)

• 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
• On the Maximum Edge Coloring Problem
• Approximating the max-edge-coloring problem
• Improved approximation algorithms for the max edge-coloring problem
• Approximating the max edge-coloring problem
• Algorithms and Computation
• 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)