Sum edge coloring of multigraphs via configuration LP

DOI10.1145/1921659.1921668MaRDI QIDQ3189004zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Maxim Sviridenko, Guy Kortsarz

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1921659.1921668

zbMATH Keywords

approximation algorithmsconfiguration LPedge scheduling

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)

Recommendations

• Min Sum Edge Coloring in Multigraphs Via Configuration LP
• Sum Multicoloring of Graphs
• Minimum Color Sum of Bipartite Graphs
• Approximation and Online Algorithms
• Minimum sum multicoloring on the edges of trees

Cited in

(6)

• On the performance guarantee of first fit for sum coloring
• Scheduling problems over a network of machines
• Min Sum Edge Coloring in Multigraphs Via Configuration LP
• Scheduling problems over network of machines
• Approximation and Online Algorithms
• Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs

This page was built for publication: Sum edge coloring of multigraphs via configuration LP

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