On chromatic sums and distributed resource allocation
From MaRDI portal
Publication:1383159
DOI10.1006/inco.1997.2677zbMath0895.68022OpenAlexW1978007997MaRDI QIDQ1383159
Tami Tamir, Mihir Bellare, Hadas Shachnai, Magnús M. Halldórsson, Amotz Bar-Noy
Publication date: 27 September 1998
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/06d74b25a12d4b88050001edfcf07eb79a20af0d
Related Items
On the performance guarantee of first fit for sum coloring, Edge-chromatic sum of trees and bounded cyclicity graphs, Ignorant vs. Anonymous Recommendations, A General Framework for Approximating Min Sum Ordering Problems, Time slot scheduling of compatible jobs, Minimum sum coloring problem: upper bounds for the chromatic strength, Chromatic Edge Strength of Some Multigraphs, Min Sum Edge Coloring in Multigraphs Via Configuration LP, Multicoloring trees., Minimum sum set coloring of trees and line graphs of trees, Batch Coloring Flat Graphs and Thin, Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs, Batch Coloring of Graphs, A new ant colony optimization algorithm for the lower bound of sum coloring problem, Non-clairvoyant scheduling with conflicts for unit-size jobs, On sum edge-coloring of regular, bipartite and split graphs, On a local protocol for concurrent file transfers, A branch-and-price algorithm for the minimum sum coloring problem, OVSF-CDMA code assignment in wireless ad hoc networks, Preemptive and non-preemptive generalized min sum set cover, Evaluation of monotone DNF formulas, Batch coloring of graphs, Computing lower bounds for minimum sum coloring and optimum cost chromatic partition, An effective heuristic algorithm for sum coloring of graphs, A short proof of the NP-completeness of minimum sum interval coloring, On the probabilistic minimum coloring and minimum \(k\)-coloring, Bounds on contention management algorithms, The maximum saving partition problem, Minimum sum edge colorings of multicycles, Unnamed Item, A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph, On integrating an iterated variable neighborhood search within a bi-objective genetic algorithm: sum coloring of graphs case application, On competitive recommendations, On the minimum sum coloring of \(P_4\)-sparse graphs, On sum coloring of graphs, Certain chromatic sums of some cycle-related graph classes, Combinatorial algorithms for data migration to minimize average completion time, Complexity results for minimum sum edge coloring, Max-optimal and sum-optimal labelings of graphs, On sum coloring and sum multi-coloring for restricted families of graphs, Weighted sum coloring in batch scheduling of conflicting jobs, Minimum Sum Coloring of P4-sparse graphs, A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Upper bounds for static resource allocation in a distributed system
- Approximating maximum independent sets by excluding subgraphs
- On the sum coloring problem on interval graphs
- Parallel concepts in graph theory
- The chromatic sum of a graph: history and recent developments
- Efficient asynchronous distributed symmetry breaking
- A Heuristic of Scheduling Parallel Tasks and Its Analysis
- Bounds for Multiprocessor Scheduling with Resource Constraints
- Approximation results for the optimum cost chromatic partition problem
- What can be computed locally?
- On the hardness of approximating minimization problems
