Multicoloring trees.

DOI10.1016/S0890-5401(02)00032-9MaRDI QIDQ1401922zbMATH OpenOpenAlexFDO

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

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

Approximation algorithmsMulticoloringResource allocationScheduling

Mathematics Subject Classification ID

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

Recommendations

• Sum Multicoloring of Graphs
• Minimum sum multicoloring on the edges of trees
• scientific article; zbMATH DE number 1929966
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• Approximation and Online Algorithms

Cites work

• scientific article; zbMATH DE number 1033414 (Why is no real title available?)
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• Minimum Color Sum of Bipartite Graphs
• On chromatic sums and distributed resource allocation
• Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems
• Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is \cal NP-Complete
• Sum Multicoloring of Graphs
• The chromatic sum of a graph: history and recent developments
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• Upper bounds for static resource allocation in a distributed system
• Zero knowledge and the chromatic number

Cited in

(23)

• Graph multi-coloring for a job scheduling application
• Scheduling jobs on identical machines with agreement graph
• Optimal shift coloring of trees
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• Window-based greedy contention management for transactional memory: theory and practice
• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
• A competitive analysis for balanced transactional memory workloads
• Bandwidth consecutive multicolorings of graphs
• Multi-coloring and job-scheduling with assignment and incompatibility costs
• Minimum sum multicoloring on the edges of trees
• Scheduling: agreement graph vs resource constraints
• Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints
• Asynchronous coordination under preferences and constraints
• Sum Multicoloring of Graphs
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• scientific article; zbMATH DE number 1929966 (Why is no real title available?)
• scientific article; zbMATH DE number 1418267 (Why is no real title available?)
• Tight lower bounds for the complexity of multicoloring
• Automata, Languages and Programming
• Minimum sum set coloring of trees and line graphs of trees
• Scheduling with conflicts: Online and offline algorithms
• Minimally colored trees

This page was built for publication: Multicoloring trees.

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