Reduction and local search for weighted graph coloring problem
The weighted graph coloring problem (WGCP) is an important extension of the graph
coloring problem (GCP) with wide applications. Compared to GCP, where numerous …
coloring problem (GCP) with wide applications. Compared to GCP, where numerous …
Weighted coloring: further complexity and approximability results
B Escoffier, J Monnot, VT Paschos - Information Processing Letters, 2006 - Elsevier
Given a vertex-weighted graph G=(V, E; w), w (v)⩾ 0 for any v∈ V, we consider a weighted
version of the coloring problem which consists in finding a partition S=(S1,…, Sk) of the …
version of the coloring problem which consists in finding a partition S=(S1,…, Sk) of the …
Approximation algorithms for the max-coloring problem
SV Pemmaraju, R Raman - International Colloquium on Automata …, 2005 - Springer
Given a graph G=(V, E) and positive integral vertex weights w: V→ N, the max-coloring
problem seeks to find a proper vertex coloring of G whose color classes C 1, C 2,..., C k …
problem seeks to find a proper vertex coloring of G whose color classes C 1, C 2,..., C k …
Online interval coloring and variants
L Epstein, M Levy - … : 32nd International Colloquium, ICALP 2005, Lisbon …, 2005 - Springer
We study interval coloring problems and present new upper and lower bounds for several
variants. We are interested in four problems, online coloring of intervals with and without …
variants. We are interested in four problems, online coloring of intervals with and without …
Memory allocation for neural networks using graph coloring
L Barenboim, R Drucker, O Zatulovsky… - Proceedings of the 23rd …, 2022 - dl.acm.org
The Memory Allocation problem for neural networks can be represented as a two-
dimensional optimization problem. The neural network is allocated into limited memory …
dimensional optimization problem. The neural network is allocated into limited memory …
A one-to-one correspondence between colorings and stable sets
D Cornaz, V Jost - Operations Research Letters, 2008 - Elsevier
Given a graph G, we construct an auxiliary graph G̃ with m¯ vertices such that the set of all
stable sets of G̃ is in one-to-one correspondence with the set of all colorings of G. Then, we …
stable sets of G̃ is in one-to-one correspondence with the set of all colorings of G. Then, we …
[HTML][HTML] First-fit coloring on interval graphs has performance ratio at least 5
HA Kierstead, DA Smith, WT Trotter - European Journal of Combinatorics, 2016 - Elsevier
First-fit is the online graph coloring algorithm that considers vertices one at a time in some
order and assigns each vertex the least positive integer not used already on a neighbor. The …
order and assigns each vertex the least positive integer not used already on a neighbor. The …
Application of copula and copula-CVaR in the multivariate portfolio optimization
M Bai, L Sun - International Symposium on Combinatorics, Algorithms …, 2007 - Springer
In this article we resort to the copula theory and CVaR measures in the portfolio
management, using copula function and copula-CVaR to design the portfolio optimization …
management, using copula function and copula-CVaR to design the portfolio optimization …
[HTML][HTML] Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
We study complexity and approximation of min weighted node coloring in planar, bipartite
and split graphs. We show that this problem is NP-hard in planar graphs, even if they are …
and split graphs. We show that this problem is NP-hard in planar graphs, even if they are …
On the first-fit chromatic number of graphs
The first-fit chromatic number of a graph is the number of colors needed in the worst case of
a greedy coloring. It is also called the Grundy number, which is defined to be the maximum …
a greedy coloring. It is also called the Grundy number, which is defined to be the maximum …