Minimum sum multicoloring on the edges of trees

DOI10.1016/J.TCS.2006.05.006MaRDI QIDQ2503344zbMATH OpenOpenAlexFDO

Authors Dániel Marx

Publication date 14 September 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.05.006

zbMATH Keywords

approximation schemeedge coloringmulticoloringtrees

Mathematics Subject Classification ID

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

Recommendations

• Approximation and Online Algorithms
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 1929966
• Edge-chromatic sum of trees and bounded cyclicity graphs
• Complexity results for minimum sum edge coloring

Cites work

• Approximation results for the optimum cost chromatic partition problem
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of scheduling multiprocessor tasks with prespecified processors allocations
• Edge-chromatic sum of trees and bounded cyclicity graphs
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• Multicoloring trees.
• On sum coloring of graphs
• Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
• Scheduling File Transfers
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Sum Multicoloring of Graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

Cited in

(13)

• List edge multicoloring in graphs with few cycles
• On chromatic sums and distributed resource allocation
• Multicoloring trees.
• Edge-chromatic sum of trees and bounded cyclicity graphs
• Sum edge coloring of multigraphs via configuration LP
• Min Sum Edge Coloring in Multigraphs Via Configuration LP
• Minimum cost edge-colorings of trees can be reduced to matchings
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• Coloring of trees with minimum sum of colors
• On a local protocol for concurrent file transfers
• Approximation and Online Algorithms
• Approximation and Online Algorithms
• Minimum sum set coloring of trees and line graphs of trees

This page was built for publication: Minimum sum multicoloring on the edges of trees

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