Geodesic
A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring
Daniel Berend1 ; Shaked Mamana1
1 Ben-Gurion University
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 365-383.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Given a graph $G$ and positive integers $b$ and $w$, the Black-and-White Coloring problem asks about the existence of a partial vertex-coloring of $G$, with $b$ vertices colored black and $w$ white, such that there is no edge between a black and a white vertex. The problem is known to be NP-complete. In this paper, we deal with the optimization version, mainly for random graphs. Using the method of conditional expectations, we develop a heuristic with a good performance. We also obtain theoretical results on some of the relevant quantities, and compare the performance of the heuristic with that of several others.
DOI : 10.7155/jgaa.v28i1.2964
Keywords: anticoloring, random graphs, denormalization

Daniel Berend 1 ; Shaked Mamana 1

1 Ben-Gurion University 
@article{JGAA_2024_28_1_a14,
     author = {Daniel Berend and Shaked Mamana},
     title = {A {Greedy} {Probabilistic} {Heuristic} for {Graph} {Black-and-White} {Anticoloring}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {365--383},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2964},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2964/}
}
TY  - JOUR
AU  - Daniel Berend
AU  - Shaked Mamana
TI  - A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 365
EP  - 383
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2964/
DO  - 10.7155/jgaa.v28i1.2964
LA  - en
ID  - JGAA_2024_28_1_a14
ER  - 
%0 Journal Article
%A Daniel Berend
%A Shaked Mamana
%T A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring
%J Journal of Graph Algorithms and Applications
%D 2024
%P 365-383
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2964/
%R 10.7155/jgaa.v28i1.2964
%G en
%F JGAA_2024_28_1_a14
Daniel Berend; Shaked Mamana. A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 365-383. doi : 10.7155/jgaa.v28i1.2964. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2964/

Cité par Sources :