A greedy probabilistic heuristic for graph black-and-white anticoloring

DOI10.7155/JGAA.V28I1.2964MaRDI QIDQ6616239zbMATH OpenFDO

Authors Daniel Berend, Shaked Mamana

Publication date 8 October 2024

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

random graphsanticoloringdenormalization

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• The Black-and-White Coloring Problem on Trees
• An improved algorithm for the black-and-white coloring problem on trees
• The black-and-white coloring problem on chordal graphs
• The probabilistic minimum coloring problem (extended abstract)
• On the probabilistic minimum coloring and minimum k-coloring

Cites work

• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A Reduction of the Anticoloring Problem to Connected Graphs
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• Anticoloring and separation of graphs
• Anticoloring of a family of grid graphs
• Anticoloring of the rook's graph
• Random graphs.
• Splitting trees
• Tabu search for the BWC problem
• The Black-and-White Coloring Problem on Trees
• The black-and-white coloring problem on chordal graphs

This page was built for publication: A greedy probabilistic heuristic for graph black-and-white anticoloring

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