Multicoloring trees.

DOI10.1016/S0890-5401(02)00032-9zbMath1054.68016OpenAlexW2913829344MaRDI QIDQ1401922

Hadas Shachnai, Magnús M. Halldórsson, Andrzej Proskurowski, Jan Arne Telle, Ravit Salman, Guy Kortsarz

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(02)00032-9

zbMATH Keywords

Resource allocationSchedulingApproximation algorithmsMulticoloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (13)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ Scheduling: agreement graph vs resource constraints ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Window-based greedy contention management for transactional memory: theory and practice ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ A competitive analysis for balanced transactional memory workloads ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Bandwidth consecutive multicolorings of graphs ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Minimum sum multicoloring on the edges of trees ⋮ Asynchronous Coordination Under Preferences and Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Upper bounds for static resource allocation in a distributed system
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Zero knowledge and the chromatic number
• Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
• On chromatic sums and distributed resource allocation
• The chromatic sum of a graph: history and recent developments
• Minimum Color Sum of Bipartite Graphs
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Sum Multicoloring of Graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees

This page was built for publication: Multicoloring trees.