Pith. sign in

REVIEW 4 major objections 4 minor 104 references

An island-parallel ensemble metaheuristic algorithm for large graph coloring problems

T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An island-parallel ensemble of three metaheuristics, polished by tabu search, matches or beats the best-known color count on 37 of 43 large benchmark graphs and scales almost linearly to 64 processors.

desk verdict The paper's central claim is contradicted by its own tables, and the results as reported cannot be trusted without a full redo. read the letter →

arxiv 2504.15082 v1 pith:SAOY24WU submitted 2025-04-21 cs.NE

Tansel Dokeroglu , Tayfun Kucukyilmaz , Ahmet Cosar This is my paper · ORCID
classification cs.NE MSC 05C1568T2068W10
keywords graphcoloringensemblemetaheuristicislandparallelHarrisHawkOptimizationArtificialBeeColonyTeaching-Learning-BasedTabuColMPIparallelization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graph coloring asks for the fewest colors that label the vertices of a graph so that adjacent vertices never share a color, and large instances are NP-hard in practice, so heuristic search is the norm. This paper proposes PEM-Color, an island-parallel ensemble that runs three recent metaheuristics — Harris Hawk Optimization, Artificial Bee Colony, and Teaching-Learning-Based Optimization — on separate groups of processors, with the tabu-search procedure TabuCol refining every candidate solution. The paper's central claim is that the ensemble matches or beats the best-known color counts on 37 of 43 large benchmark instances and does so in practical wall-clock times, from under a second on easy instances to about half an hour on the hardest, while gaining an almost linear speed-up as processors are added. A sympathetic reader would care because this is presented as the first ensemble-of-metaheuristics treatment of graph coloring, and it offers evidence that algorithm diversity plus parallel hardware can compete with dedicated single-algorithm solvers that are often allowed days of runtime.

What carries the argument

The load-bearing mechanism is the island-parallel ensemble itself: 64 Message Passing Interface (MPI) processes form one master and 63 slaves, partitioned into three groups of 21, with each group running one metaheuristic (Harris Hawk Optimization, Artificial Bee Colony, or Teaching-Learning-Based Optimization) on a population of 20 candidate colorings, and each slave seeded differently so the same metaheuristic explores many parameter settings at once. TabuCol acts as a local-search polish applied to every candidate after each generation. The master receives only the best solution from each slave at generation boundaries, keeping communication near zero, which is what allows near-linear speed-up. The ensemble exploits the no-free-lunch observation that no single metaheuristic dominates all instances: different islands are expected to lead on different graphs, and the master's simple choose-the-best rule selects the winner.

What would settle it

Independently verify the reported colorings, especially the four where Table 3 shows a count below the stated best-known value (C2000.5 at 148 colors, C4000.5 at 272, DSJC500.5 at 48, DSJC1000.9 at 223): check every edge to confirm no two endpoints share a color, and reconcile the different values Table 4 lists for the same instances (301, 49, and 226). If any adjacent pair shares a color, or if the Table 4 values are the real outputs, the claimed improvement over best-known solutions is not established.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that three complementary population-based search methods — Harris Hawk Optimization, Artificial Bee Colony, and Teaching-Learning-Based Optimization — can be wrapped in a master-slave parallel ensemble, with the TabuCol local search polishing every candidate, so that the combined search is at least as good as thirteen published graph-coloring algorithms on the standard large benchmark instances. The design runs 63 slaves in three groups of 21, one group per metaheuristic, each slave using its own random seed; the master collects only the best solution from each slave at generation boundaries. The paper reports exact matches of the best-known color counts on all 19 small instances, best-known or better counts on 18 of 24 large instances, and a total used-color count only 1.84 percent above the sum of the best-known values for the large set, together with an almost linear speed-up in fitness evaluations on 64 processors. If these numbers hold, the contribution is a recipe for turning metaheuristic diversity into state-of-the-art graph coloring without letting communication overhead eat the parallelism.

Load-bearing premise

The paper's headline comparison rests on the assumption that every color count it reports in Table 3 is a valid proper coloring and that the best-known values it compares against are correct; if the entries that appear better than the stated best-known values are errors, the claim of best results in 37 out of 43 instances collapses.

Editorial extensions

If this is right

  • If the 37-of-43 result holds, PEM-Color sits with the strongest published graph-coloring algorithms on large instances while using a fraction of their wall-clock time.
  • The almost linear speed-up means the ensemble's 64 processors deliver roughly 64 times as many fitness evaluations in the same wall-clock time, so buying more cores is a direct way to shorten the search.
  • Because different islands run different metaheuristics with different random seeds, a graph that stalls one metaheuristic can still be solved by another island, which is a practical hedge against the no-free-lunch principle.
  • Since every candidate is polished by TabuCol, the ensemble's advantage is best understood as a diversification layer on top of a strong tabu-search core, not as a replacement for local search.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the Table 3 entries that are lower than the stated best-known values (for instance 148 colors on C2000.5 against a stated best of 153) are valid proper colorings, they would be new record upper bounds; the paper never says so explicitly, and independent verification is the natural next step.
  • The same island-ensemble wrapper could be lifted onto other NP-hard problems the paper names, such as traveling salesman or maximum clique, because the wrapper only needs a fitness function and a local-search polisher; a port would test whether ensemble diversity, not the specific metaheuristics, is the active ingredient.
  • The current design gives each metaheuristic the same number of islands regardless of instance difficulty; an adaptive scheduler that reassigns processors to the metaheuristic making the fastest progress is a testable extension that could improve both time and final color count.
  • The speed-up evidence is presented as a count of fitness evaluations rather than as a measured wall-clock scaling curve; running the same instances with 8, 16, 32, and 64 processors would confirm whether communication overhead really stays under the reported 5 percent.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes PEM-Color, an island-parallel ensemble metaheuristic that combines Harris Hawk Optimization, Artificial Bee Colony, and Teaching-Learning-Based Optimization with a TabuCol local search to solve large DIMACS graph coloring instances using MPI. The authors report results for 43 instances, claim a near-linear speed-up on 64 processors, and state in the abstract and introduction that PEM-Color outperforms 13 state-of-the-art algorithms and achieves the best known solutions in 37 of 43 instances.

Significance. If the reported results were reproducible, the paper would offer a useful contribution to parallel metaheuristics for graph coloring, and the island-parallel ensemble design is a plausible way to combine complementary search strategies. The authors also correctly identify that the GCP literature lacks parallel ensemble approaches based on these three metaheuristics. However, the manuscript's central empirical claims are not supported by its own tables: Table 3 and Table 4 report different PEM-Color outcomes for the same instances, the k* column contains values contradicted by the paper's own comparison table, and the claimed superiority over 13 state-of-the-art algorithms is contradicted by Table 4, where PEM-Color never achieves the unique best value on any instance. No code, raw outputs, or verifier for the colorings are provided, so the contradictions cannot be resolved from the manuscript alone.

major comments (4)
  1. [§4.2, Table 3 vs. §4.3, Table 4] The two main result tables are irreconcilable for the same instances. Table 3 reports k=148 for C2000.5 while Table 4 lists PEM-Color as 153; Table 3 reports k=272 for C4000.5 while Table 4 lists 301; Table 3 reports k=48 for DSJC500.5 while Table 4 lists 49; and Table 3 reports k=223 for DSJC1000.9 while Table 4 lists 226. The narrative in §4.2 states that 2040 colors were used with a best-known total of 2003, but the sum of the Table 3 k column is 1994, whereas 2040 is exactly the sum of the Table 4 PEM-Color row. Because the central claim of 'best results in 37 out of 43' depends on which table is accepted, the manuscript as submitted does not support its abstract's claims.
  2. [Abstract and §4.3, Table 4] The claim that PEM-Color 'outperforms 13 state-of-the-art algorithms' is contradicted by the paper's own comparison. In Table 4, PEM-Color ties or loses to at least one comparator on every row and never achieves the best value by itself: C2000.5 loses to Evocol (151) and MACOL (148); DSJC500.5 loses to VSS, Foopar, HEA, AMACOL, MMT, Evocol, and MACOL (48); DSJC1000.5 loses to HEA, MMT, Evocol, and MACOL (83); DSJR500.5 loses to PCNS, MMT, MIPS, Evocol, and MACOL (122); R1000.5 loses to MMT (234). Thus, even setting aside the Table 3/Table 4 conflict, the comparative statement in the abstract and introduction is not supported by the evidence the authors present.
  3. [Table 3, k* column] The best-known values listed in Table 3 are internally inconsistent with Table 4. Table 3 lists k*=153 for C2000.5, but Table 4 reports MACOL at 148 and Evocol at 151; Table 3 lists k*=280 for C4000.5, but Table 4 reports MACOL at 272; Table 3 lists k*=49 for DSJC500.5, but Table 4 reports six algorithms at 48. If the Table 3 values are correct, then the paper reports new best-known colorings (e.g., C2000.5 at 148, DSJC500.5 at 48, DSJC1000.9 at 223) and must flag them as such, but it never does. If they are incorrect, the '37 more colors' calculation and the '37 out of 43' claim are not meaningful.
  4. [§4.4, scalability and speed-up analysis] The strong and linear scalability claim is not backed by experimental evidence. The section asserts an 'almost linear speed-up' and that MPI overhead is 'not more than 5%', but it reports no speed-up curve, no strong/weak scaling experiments, and no comparison of parallel execution time against a sequential implementation of the same algorithm. The observation that 64 processors perform 1,280,000 fitness evaluations while each processor performs 20,000 is an aggregate throughput statement that follows directly from the experimental design, not a speed-up result, and it does not control for solution quality or communication cost.
minor comments (4)
  1. [§4.2] The sentence 'We used 2040 colors to paint all these graphs in Table 2' is inconsistent with the content: Table 2 is the small-instance table, and the 2040 total matches the Table 4 PEM-Color row, not the Table 3 column. This typo adds to the confusion caused by the table discrepancies.
  2. [Table 1 and §3.1] Section 3.1 states that parameters are 'randomly selected within the defined ranges', but the paper never specifies these ranges, and Table 1 only lists fixed values or qualitative descriptions (e.g., 'random' for J, 'range of (-1, 1)' for E0). This makes the reported parameter settings not fully reproducible.
  3. [Tables 2 and 3] DSJC250.5 appears in both Table 2 and Table 3 with the same k=28 but with different average times (10.214 seconds vs. 8.7 seconds). The manuscript does not explain whether these are separate experiments, different stopping conditions, or a reporting error.
  4. [References] Several references contain placeholder text '???' for publisher locations (e.g., Alba 2005, Barenboim and Elkin 2013, Jensen and Toft 2011, Talbi 2009), and some bibliographic entries are incomplete. A careful proofreading of the reference list is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the paper's claims are empirical comparisons against external DIMACS benchmarks; internal table conflicts are correctness issues, not circularity.

full rationale

The paper makes no formal derivation whose output is equivalent to its input. Its central comparisons are against externally published DIMACS best-known values and 13 independent algorithms, so the headline performance claims are externally falsifiable rather than reduced from the paper's own assumptions. The component metaheuristics (HHO, ABC, TLBO) and TabuCol are cited from the original external literature; the self-citations to Dokeroglu and Sevinc (2021, 2022) supply prior GCP-adapted variants and the statement that 'we have used previously optimized values of the HHO, ABC, and TLBO metaheuristics,' but the paper does not define the benchmark targets in terms of PEM-Color, and no fitted parameter is renamed as a prediction. The internal inconsistencies (e.g., Table 3 lists C2000.5 k=148 while Table 4 lists PEM-Color as 153; the text's 2040-color total matches Table 4, not Table 3) and the fact that Table 4 shows several competitors beating PEM-Color are serious empirical-correctness and reporting problems, but they are not circularity. Under the instruction to reserve circularity findings for demonstrated reductions, no circular step can be exhibited.

Assumptions & free parameters 8 free parameters · 5 assumptions · 0 invented entities

The central claims rest on: correct external benchmark bounds (k*), a valid adaptation of three metaheuristics to graph coloring, the assumption that TabuCol integration helps, the assumption that a parallel portfolio of independent runs constitutes an ensemble, and a set of hand-picked hyperparameters. None of these are independently verified within the paper, and the benchmark-bound assumption is directly strained by the Table 3 versus Table 4 contradictions.

free parameters (8)
  • population_size = 20
    Chosen by hand; controls exploration and exploitation balance in each metaheuristic. No sensitivity analysis provided.
  • number_of_generations = 1000
    Stopping criterion for the metaheuristics; no justification or ablation study.
  • TabuCol_depth = 100,000
    Maximum iterations for the local search; chosen by hand.
  • tabu_list_size = 7
    Tabu search parameter; the paper says it is 'assumed to be seven' without sensitivity analysis.
  • HHO_initial_energy_range_E0 = (-1, 1)
    Defines the exploration/exploitation phases in HHO; standard but effectively free.
  • ABC_onlooker_ratio = 50%
    Fraction of onlooker bees; taken from standard ABC, not tuned for GCP.
  • scout_bees_count = 1
    Number of scout bees in ABC; standard setting.
  • teachers_count = 1
    Number of teachers in TLBO; standard setting.
assumptions (5)
  • domain assumption The DIMACS benchmark instances and the k* (best-known chromatic number) values quoted in Tables 2 and 3 are correct and authoritative.
    The entire comparison rests on these external bounds. The paper never questions them, yet several Table 3 entries report k values below the quoted k*, which would be new records.
  • domain assumption The three metaheuristics (HHO, ABC, TLBO) can be correctly adapted to the graph coloring problem using the described operators.
    Section 3 describes feature-transfer operations only in general terms for HHO and gives high-level bee/teacher analogies for ABC and TLBO. No formal description proves these operators preserve a valid coloring.
  • domain assumption The TabuCol local search improves solution quality when applied to every candidate solution in every generation.
    TabuCol is a known method, but the paper does not test whether its application inside each metaheuristic helps or hurts, nor how its depth interacts with the outer search.
  • ad hoc to paper The MPI communication overhead is small and the speedup can be inferred from a linear scaling of fitness evaluations.
    Section 4.4 asserts 'not more than 5% execution times' overhead without presenting measured communication time or a sequential baseline, and equates the number of fitness evaluations with speedup.
  • ad hoc to paper Seeding each processor's random number generator with its processor id provides beneficial diversification.
    The paper states this was 'observed to provide a good diversification' but gives no comparative experiment.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An island-parallel ensemble metaheuristic algorithm for large graph coloring problems." pith.science (2026). https://pith.science/paper/SAOY24WU

@misc{pith2026250415082,
  author       = {Pith},
  title        = {Pith review of: An island-parallel ensemble metaheuristic algorithm for large graph coloring problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SAOY24WU}},
  note         = {Machine review of arXiv:2504.15082}
}
read the original abstract

Graph Coloring Problem (GCP) is an NP-Hard vertex labeling problem in graphs such that no two adjacent vertices can have the same color. Large instances of GCP cannot be solved in reasonable execution times by exact algorithms. Therefore, soft computing approaches, such as metaheuristics, have proven to be very efficient for solving large instances of GCP. In this study, we propose a new island-parallel ensemble metaheuristic algorithm (PEM-Color) to solve large GCP instances. Ensemble learning is a new machine learning approach based on combining the output of multiple models instead of using a single one. We use Message Passing Interface (MPI) parallel computation libraries to combine recent state-of-the-art metaheuristics: Harris Hawk Optimization (HHO), Artificial Bee Colony (ABC), and Teaching Learning Based (TLBO) to improve the quality of their solutions further. To the best of our knowledge, this is the first study that combines metaheuristics and applies to the GCP using an ensemble approach. We conducted experiments on large graph instances from the well-known DIMACS benchmark using 64 processors and achieved significant improvements in execution times. The experiments also indicate an almost linear speed-up with a strong scalability potential. The solution quality of the instances is promising, as our algorithm outperforms 13 state-of-the-art algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

104 extracted references · 65 canonical work pages

  1. [1]

    , Agrawal , S

    barticle Agrawal , J. , Agrawal , S. : Acceleration based particle swarm optimization for graph coloring problem . Procedia Computer Science 60 , 714 -- 721 ( 2015 ) barticle

    2015

  2. [2]

    , Burtscher , M

    barticle Alabandi , G. , Burtscher , M. : Improving the speed and quality of parallel graph coloring . ACM Transactions on Parallel Computing 9 ( 3 ), 1 -- 35 ( 2022 ) barticle

    2022

  3. [3]

    , Bordawekar , R

    botherref Allwright , J. , Bordawekar , R. , Coddington , P. , Dincer , K. , Martin , C. : A comparison of parallel graph coloring algorithms. SCCS-666, 1--19 (1995) botherref

    1995

  4. [4]

    : Applications of graph coloring in modern computer science

    barticle Ahmed , S. : Applications of graph coloring in modern computer science . International Journal of Computer and Information Technology 3 ( 2 ), 1 -- 7 ( 2012 ) barticle

    2012

  5. [5]

    , Indra , Z

    barticle Ananda , R. , Indra , Z. , Nasution , H. : Application of graph coloring on nurse work scheduling at h. adam malik hospital medan using the tabu search algorithm . ZERO: Jurnal Sains, Matematika dan Terapan 6 ( 1 ), 1 -- 8 ( 2022 ) barticle

    2022

  6. [6]

    : Parallel Metaheuristics: a New Class of Algorithms

    bbook Alba , E. : Parallel Metaheuristics: a New Class of Algorithms . John Wiley & Sons , ??? ( 2005 ) bbook

    2005

  7. [7]

    , Luque , G

    barticle Alba , E. , Luque , G. , Nesmachnow , S. : Parallel metaheuristics: recent advances and new trends . International Transactions in Operational Research 20 ( 1 ), 1 -- 48 ( 2013 ) barticle

    2013

  8. [8]

    , Mouhoub , M

    barticle Abbasian , R. , Mouhoub , M. : A hierarchical parallel genetic approach for the graph coloring problem . Applied intelligence 39 , 510 -- 528 ( 2013 ) barticle

    2013

Show all 104 references
  1. [9]

    , Powers , E

    bchapter Alabandi , G. , Powers , E. , Burtscher , M. : Increasing the parallelism of graph coloring via shortcutting . In: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming , pp. 262 -- 275 ( 2020 ) bchapter

    2020

  2. [10]

    , Bozda g , D

    bchapter Boman , E.G. , Bozda g , D. , Catalyurek , U. , Gebremedhin , A.H. , Manne , F. : A scalable parallel graph coloring algorithm for distributed memory computers . In: Euro-Par 2005 Parallel Processing: 11th International Euro-Par Conference, Lisbon, Portugal, August 30...

    2005

  3. [11]

    , Elkin , M

    bbook Barenboim , L. , Elkin , M. : Distributed Graph Coloring: Fundamentals and Recent Developments . Morgan & Claypool Publishers , ??? ( 2013 ) bbook

    2013

  4. [12]

    , Kliesch , A

    barticle Bravyi , S. , Kliesch , A. , Koenig , R. , Tang , E. : Hybrid quantum-classical algorithms for approximate graph coloring . Quantum 6 , 678 ( 2022 ) barticle

    2022

  5. [13]

    , Laib , R

    bchapter Bessedik , M. , Laib , R. , Boulmerka , A. , Drias , H. : Ant colony system for graph coloring problem . In: International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologi...

    2005

  6. [14]

    , Lepagnot , J

    barticle Boussa \" d , I. , Lepagnot , J. , Siarry , P. : A survey on optimization metaheuristics . Information sciences 237 , 82 -- 117 ( 2013 ) barticle

    2013

  7. [15]

    , McCollum , B

    barticle Burke , E.K. , McCollum , B. , Meisels , A. , Petrovic , S. , Qu , R. : A graph-based hyper-heuristic for educational timetabling problems . European journal of operational research 176 ( 1 ), 177 -- 192 ( 2007 ) barticle

    2007

  8. [16]

    , Slota , G.M

    barticle Bogle , I. , Slota , G.M. , Boman , E.G. , Devine , K.D. , Rajamanickam , S. : Parallel graph coloring algorithms for distributed gpu environments . Parallel Computing 110 , 102896 ( 2022 ) barticle

    2022

  9. [17]

    , Zufferey , N

    barticle Bl \"o chliger , I. , Zufferey , N. : A graph coloring heuristic using partial solutions and a reactive tabu scheme . Computers & Operations Research 35 ( 3 ), 960 -- 975 ( 2008 ) barticle

    2008

  10. [18]

    , Dagum , L

    botherref Chandra , R. , Dagum , L. , Kohr , D. , Mayden , D. : Parallel programming in openmp. NY.: Morgan Kaufmann Publishers (2008) botherref

    2008

  11. [19]

    u rek , \

    barticle C ataly \"u rek , \"U .V. , Feo , J. , Gebremedhin , A.H. , Halappanavar , M. , Pothen , A. : Graph coloring algorithms for multi-core and massively multithreaded architectures . Parallel Computing 38 ( 10-11 ), 576 -- 594 ( 2012 ) barticle

    2012

  12. [20]

    , Kanefsky , B

    bchapter Cheeseman , P.C. , Kanefsky , B. , Taylor , W.M. , : Where the really hard problems are. In: Ijcai , vol. 91 , pp. 331 -- 337 ( 1991 ) bchapter

    1991

  13. [21]

    , Li , P

    barticle Chen , X. , Li , P. , Fang , J. , Tang , T. , Wang , Z. , Yang , C. : Efficient and high-quality sparse graph coloring on gpus . Concurrency and Computation: Practice and Experience 29 ( 10 ), 4064 ( 2017 ) barticle

    2017

  14. [22]

    , St \"u tzle , T

    bchapter Chiarandini , M. , St \"u tzle , T. , : An application of iterated local search to graph coloring problem . In: Proceedings of the Computational Symposium on Graph Coloring and Its Generalizations , pp. 112 -- 125 ( 2002 ). Ithaca New York (USA) bchapter

    2002

  15. [23]

    , : Ensemble learning

    barticle Dietterich , T.G. , : Ensemble learning . The handbook of brain theory and neural networks 2 ( 1 ), 110 -- 125 ( 2002 ) barticle

    2002

  16. [24]

    , Boman , E.G

    bchapter Deveci , M. , Boman , E.G. , Devine , K.D. , Rajamanickam , S. : Parallel graph coloring for manycore architectures . In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) , pp. 892 -- 901 ( 2016 ). 10.1109/IPDPS.2016.54 bchapter

    2016 doi

  17. [25]

    , Birattari , M

    barticle Dorigo , M. , Birattari , M. , Stutzle , T. : Ant colony optimization . IEEE Computational Intelligence Magazine 1 ( 4 ), 28 -- 39 ( 2006 ) 10.1109/MCI.2006.329691 barticle

    2006

  18. [26]

    , Dias , B

    barticle Freitas , R. , Dias , B. , Maculan , N. , Szwarcfiter , J. : On distance graph coloring problems . International Transactions in Operational Research 28 ( 3 ), 1213 -- 1241 ( 2021 ) barticle

    2021

  19. [27]

    , Guha , R

    botherref Datta , D. , Guha , R. , Banerjee , N. , Adhikary , S. , Acharya , A. : Examination scheduler using a linear-time graph coloring algorithm. ICTACT Journal on Soft Computing 12(4) (2022) botherref

    2022

  20. [28]

    , Hao , J.-K

    bchapter Dorne , R. , Hao , J.-K. : Tabu search for graph coloring, t-colorings and set t-colorings . In: Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization , pp. 77 -- 92 . Springer , ??? ( 1999 ) bchapter

    1999

  21. [29]

    , Markib , H.Y

    bchapter Dorrigiv , M. , Markib , H.Y. : Algorithms for the graph coloring problem based on swarm intelligence . In: The 16th CSI International Symposium on Artificial Intelligence and Signal Processing (AISP 2012) , pp. 473 -- 478 ( 2012 ). IEEE bchapter

    2012

  22. [30]

    , Sevinc , E

    barticle Dokeroglu , T. , Sevinc , E. : Memetic teaching--learning-based optimization algorithms for large graph coloring problems . Engineering Applications of Artificial Intelligence 102 , 104282 ( 2021 ) barticle

    2021

  23. [31]

    , Sevinc , E

    barticle Dokeroglu , T. , Sevinc , E. : An island parallel harris hawks optimization algorithm . Neural Computing and Applications 34 ( 21 ), 18341 -- 18368 ( 2022 ) barticle

    2022

  24. [32]

    , Sabba , S

    bchapter Djelloul , H. , Sabba , S. , Chikhi , S. : Binary bat algorithm for graph coloring problem . In: 2014 Second World Conference on Complex Systems (WCCS) , pp. 481 -- 486 ( 2014 ). 10.1109/ICoCS.2014.7060988 bchapter

    2014

  25. [33]

    : A new representation and operators for genetic algorithms applied to grouping problems

    barticle Falkenauer , E. : A new representation and operators for genetic algorithms applied to grouping problems . Evolutionary computation 2 ( 2 ), 123 -- 144 ( 1994 ) barticle

    1994

  26. [34]

    , Higashino , T

    barticle Funabiki , N. , Higashino , T. : A minimal-state processing search algorithm for graph coloring problems . IEICE transactions on fundamentals of electronics, communications and computer sciences 83 ( 7 ), 1420 -- 1430 ( 2000 ) barticle

    2000

  27. [35]

    : Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability

    barticle Fleurent , C. : Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability . DIMACS Ser. Discrete Math. 26 , 619 -- 652 ( 1996 ) barticle

    1996

  28. [36]

    , Grelier , C

    barticle Goudet , O. , Grelier , C. , Hao , J.-K. : A deep learning guided memetic framework for graph coloring problems . Knowledge-Based Systems 258 , 109986 ( 2022 ) 10.1016/j.knosys.2022.109986 barticle

    2022

  29. [37]

    , Hao , J.-K

    barticle Galinier , P. , Hao , J.-K. : Hybrid evolutionary algorithms for graph coloring . Journal of combinatorial optimization 3 , 379 -- 397 ( 1999 ) barticle

    1999

  30. [38]

    , Hertz , A

    barticle Galinier , P. , Hertz , A. : A survey of local search methods for graph coloring . Computers & Operations Research 33 ( 9 ), 2547 -- 2562 ( 2006 ) barticle

    2006

  31. [39]

    , Hertz , A

    barticle Gamache , M. , Hertz , A. , Ouellet , J.O. : A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding . Computers & operations research 34 ( 8 ), 2384 -- 2395 ( 2007 ) barticle

    2007

  32. [40]

    , Hertz , A

    barticle Galinier , P. , Hertz , A. , Zufferey , N. : An adaptive memory algorithm for the k-coloring problem . Discrete Applied Mathematics 156 ( 2 ), 267 -- 279 ( 2008 ) barticle

    2008

  33. [41]

    barticle Gjertsen, Jr. , R.K. , Jones , M.T. , Plassmann , P.E. : Parallel heuristics for improved, balanced graph colorings . Journal of Parallel and Distributed Computing 37 ( 2 ), 171 -- 186 ( 1996 ) 10.1006/jpdc.1996.0117 barticle

    1996

  34. [42]

    , Lee , E.J

    bchapter Gaspers , S. , Lee , E.J. : Faster graph coloring in polynomial space . In: International Computing and Combinatorics Conference , pp. 371 -- 383 ( 2017 ). Springer bchapter

    2017

  35. [43]

    , Manne , F

    barticle Gebremedhin , A.H. , Manne , F. : Scalable parallel graph coloring algorithms . Concurrency: Practice and Experience 12 ( 12 ), 1131 -- 1146 ( 2000 ) barticle

    2000

  36. [44]

    , Manne , F

    bchapter Gebremedhin , A.H. , Manne , F. , Woods , T. : Speeding up parallel graph coloring . In: Applied Parallel Computing. State of the Art in Scientific Computing: 7th International Workshop, PARA 2004, Lyngby, Denmark, June 20-23, 2004. Revised Selected Papers 7 , pp. 107...

    2004

  37. [45]

    , Peppas , A

    barticle Giannoula , C. , Peppas , A. , Goumas , G. , Koziris , N. : High-performance and balanced parallel graph coloring on multicore platforms . The Journal of Supercomputing 79 ( 6 ), 6373 -- 6421 ( 2023 ) barticle

    2023

  38. [46]

    , Zhu , P

    bchapter Grosset , A.V.P. , Zhu , P. , Liu , S. , Venkatasubramanian , S. , Hall , M. : Evaluating graph coloring on gpus . In: Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming , pp. 297 -- 298 ( 2011 ) bchapter

    2011

  39. [47]

    , Faris , H

    barticle Hijazi , N.M. , Faris , H. , Aljarah , I. : A parallel metaheuristic approach for ensemble feature selection based on multi-core architectures . Expert Systems with Applications 182 , 115290 ( 2021 ) barticle

    2021

  40. [48]

    , Kaler , T

    bchapter Hasenplaugh , W. , Kaler , T. , Schardl , T.B. , Leiserson , C.E. : Ordering heuristics for parallel graph coloring . In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures , pp. 166 -- 177 ( 2014 ) bchapter

    2014

  41. [49]

    , Li , Y

    barticle Huang , C. , Li , Y. , Yao , X. : A survey of automatic parameter tuning methods for metaheuristics . IEEE transactions on evolutionary computation 24 ( 2 ), 201 -- 216 ( 2019 ) barticle

    2019

  42. [50]

    , Mirjalili , S

    barticle Heidari , A.A. , Mirjalili , S. , Faris , H. , Aljarah , I. , Mafarja , M. , Chen , H. : Harris hawks optimization: Algorithm and applications . Future generation computer systems 97 , 849 -- 872 ( 2019 ) barticle

    2019

  43. [51]

    , Patwary , M

    botherref Huang , J. , Patwary , M. , Diamos , G. : Coloring big graphs with alphagozero. arXiv preprint arXiv:1902.10162 (2019) botherref

    2019 arXiv

  44. [52]

    , Plumettaz , M

    barticle Hertz , A. , Plumettaz , M. , Zufferey , N. : Variable space search for graph coloring . Discrete Applied Mathematics 156 ( 13 ), 2551 -- 2560 ( 2008 ) barticle

    2008

  45. [53]

    , Werra , D.d

    barticle Hertz , A. , Werra , D.d. : Using tabu search techniques for graph coloring . Computing 39 ( 4 ), 345 -- 351 ( 1987 ) barticle

    1987

  46. [54]

    , Plassmann , P.E

    barticle Jones , M.T. , Plassmann , P.E. : A parallel graph coloring heuristic . SIAM Journal on Scientific Computing 14 ( 3 ), 654 -- 669 ( 1993 ) barticle

    1993

  47. [55]

    , Trick , M.A

    bbook Johnson , D.S. , Trick , M.A. : Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993 vol. 26 . American Mathematical Soc. , ??? ( 1996 ) bbook

    1993

  48. [56]

    , Toft , B

    bbook Jensen , T.R. , Toft , B. : Graph Coloring Problems . John Wiley & Sons , ??? ( 2011 ) bbook

    2011

  49. [57]

    , Basturk , B

    barticle Karaboga , D. , Basturk , B. : On the performance of artificial bee colony (abc) algorithm . Applied soft computing 8 ( 1 ), 687 -- 697 ( 2008 ) barticle

    2008

  50. [58]

    , De , D

    bchapter Kole , A. , De , D. , Pal , A.J. : Solving graph coloring problem using ant colony optimization, simulated annealing and quantum annealing—a comparative study . In: Intelligence Enabled Research: DoSIER 2021 , pp. 1 -- 15 . Springer , ??? ( 2022 ) bchapter

    2021

  51. [59]

    , Eberhart , R

    bchapter Kennedy , J. , Eberhart , R. : Particle swarm optimization . In: Proceedings of ICNN'95-international Conference on Neural Networks , vol. 4 , pp. 1942 -- 1948 ( 1995 ). IEEE bchapter

    1942

  52. [60]

    , Kwarciany , K

    bchapter Kokosi \'n ski , Z. , Kwarciany , K. : On sum coloring of graphs with parallel genetic algorithms . In: International Conference on Adaptive and Natural Computing Algorithms , pp. 211 -- 219 ( 2007 ). Springer bchapter

    2007

  53. [61]

    , Condon , A

    botherref Lewandowski , G. , Condon , A. : Experiments with parallel graph coloring heuristics and applications of graph coloring. Cliques, Coloring, and Satisfiability 26 (1993) botherref

    1993

  54. [62]

    , Hao , J.-K

    barticle L \"u , Z. , Hao , J.-K. : A memetic algorithm for graph coloring . European Journal of Operational Research 203 ( 1 ), 241 -- 250 ( 2010 ) barticle

    2010

  55. [63]

    , Halappanavar , M

    bchapter Lu , H. , Halappanavar , M. , Chavarr \' a-Miranda , D. , Gebremedhin , A. , Kalyanaraman , A. : Balanced coloring for parallel computing applications . In: 2015 IEEE International Parallel and Distributed Processing Symposium , pp. 7 -- 16 ( 2015 ). IEEE bchapter

    2015

  56. [64]

    , Xu , J

    barticle Liu , Y. , Xu , J. , Pan , L. , Wang , S. : Dna solution of a graph coloring problem . Journal of chemical information and computer sciences 42 ( 3 ), 524 -- 528 ( 2002 ) barticle

    2002

  57. [65]

    , Khiyabani , F.M

    barticle Mostafaie , T. , Khiyabani , F.M. , Navimipour , N.J. : A systematic study on meta-heuristic approaches for solving the graph coloring problem . Computers & Operations Research 120 , 104850 ( 2020 ) barticle

    2020

  58. [66]

    , Lotfi , S

    barticle Mahmoudi , S. , Lotfi , S. : Modified cuckoo optimization algorithm (mcoa) to solve graph coloring problem . Applied soft computing 33 , 48 -- 64 ( 2015 ) barticle

    2015

  59. [67]

    , Marble , G

    bchapter Matula , D.W. , Marble , G. , Isaacson , J.D. : Graph coloring algorithms . In: Graph Theory and Computing , pp. 109 -- 122 . Elsevier , ??? ( 1972 ) bchapter

    1972

  60. [68]

    , Monaci , M

    barticle Malaguti , E. , Monaci , M. , Toth , P. : A metaheuristic approach for the vertex coloring problem . INFORMS Journal on Computing 20 ( 2 ), 302 -- 316 ( 2008 ) barticle

    2008

  61. [69]

    : Algorithms for General Graph Coloring

    bbook Morgenstern , C.A. : Algorithms for General Graph Coloring . University of New Mexico. Department of Computer Science. College of Engineering , ??? ( 1989 ) bbook

    1989

  62. [70]

    : Distributed coloration neighborhood search

    botherref Morgenstern , C. : Distributed coloration neighborhood search. Technical report, Univ. of Michigan, Ann Arbor, MI (United States) (1994) botherref

    1994

  63. [71]

    , Sugita , Y

    barticle Mitsutake , A. , Sugita , Y. , Okamoto , Y. : Generalized-ensemble algorithms for molecular simulations of biopolymers . Peptide Science: Original Research on Biomolecules 60 ( 2 ), 96 -- 123 ( 2001 ) barticle

    2001

  64. [72]

    , Castonguay , P

    botherref Naumov , M. , Castonguay , P. , Cohen , J. : Parallel graph coloring with applications to the incomplete-lu factorization on the gpu. Nvidia White Paper (2015) botherref

    2015

  65. [73]

    , Le , D.-N

    bbook Nayyar , A. , Le , D.-N. , Nguyen , N.G. : Advances in Swarm Intelligence for Optimizing Problems in Computer Science . CRC press , ??? ( 2018 ) bbook

    2018

  66. [74]

    : A fast algorithm for the maximum clique problem

    barticle \"O sterg rd , P.R. : A fast algorithm for the maximum clique problem . Discrete Applied Mathematics 120 ( 1-3 ), 197 -- 207 ( 2002 ) barticle

    2002

  67. [75]

    , Truong , M

    bchapter Osama , M. , Truong , M. , Yang , C. , Bulu c , A. , Owens , J. : Graph coloring on the gpu . In: 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) , pp. 231 -- 240 ( 2019 ). IEEE bchapter

    2019

  68. [76]

    , Hao , J.-K

    bchapter Porumbel , D.C. , Hao , J.-K. , Kuntz , P. : Diversity control and multi-parent recombination for evolutionary graph coloring algorithms . In: European Conference on Evolutionary Computation in Combinatorial Optimization , pp. 121 -- 132 ( 2009 ). Springer bchapter

    2009

  69. [77]

    , Mavridou , T

    botherref Pardalos , P.M. , Mavridou , T. , Xue , J. : The graph coloring problem: A bibliographic survey. Handbook of Combinatorial Optimization: Volume1--3, 1077--1141 (1998) botherref

    1998

  70. [78]

    , Savsani , V.J

    barticle Rao , R.V. , Savsani , V.J. , Vakharia , D. : Teaching--learning-based optimization: a novel method for constrained mechanical design optimization problems . Computer-aided design 43 ( 3 ), 303 -- 315 ( 2011 ) barticle

    2011

  71. [79]

    , Ayob , M

    barticle Sabar , N.R. , Ayob , M. , Qu , R. , Kendall , G. : A graph coloring constructive hyper-heuristic for examination timetabling problems . Applied Intelligence 37 , 1 -- 11 ( 2012 ) barticle

    2012

  72. [80]

    , Kottath , R

    barticle Singh , P. , Kottath , R. : An ensemble approach to meta-heuristic algorithms: comparative analysis and its applications . Computers & Industrial Engineering 162 , 107739 ( 2021 ) barticle

    2021

  73. [81]

    , Mori , R

    barticle Shimizu , K. , Mori , R. : Exponential-time quantum algorithms for graph coloring problems . Algorithmica 84 ( 12 ), 3603 -- 3621 ( 2022 ) barticle

    2022

  74. [82]

    u ce , A.E. , Saule , E. , C ataly \

    bchapter Sar y \"u ce , A.E. , Saule , E. , C ataly \"u rek , \"U .V. : Improving graph coloring on distributed-memory parallel computers . In: 2011 18th International Conference on High Performance Computing , pp. 1 -- 10 ( 2011 ). IEEE bchapter

    2011

  75. [83]

    : Metaheuristics: from Design to Implementation

    bbook Talbi , E.-G. : Metaheuristics: from Design to Implementation . John Wiley & Sons , ??? ( 2009 ) bbook

    2009

  76. [84]

    , Bagora , S

    barticle Thadani , S. , Bagora , S. , Sharma , A. : Applications of graph coloring in various fields . Materials Today: Proceedings 66 , 3498 -- 3501 ( 2022 ) barticle

    2022

  77. [85]

    : Graph Theory as I Have Known It vol

    bbook Tutte , W.T. : Graph Theory as I Have Known It vol. 11 . Oxford University Press , ??? ( 1998 ) bbook

    1998

  78. [86]

    : Graph coloring with decision diagrams

    barticle Hoeve , W.-J. : Graph coloring with decision diagrams . Mathematical Programming 192 ( 1-2 ), 631 -- 674 ( 2022 ) barticle

    2022

  79. [87]

    , Dongarra , J.J

    barticle Walker , D.W. , Dongarra , J.J. : Mpi: a standard message passing interface . Supercomputer 12 , 56 -- 68 ( 1996 ) barticle

    1996

  80. [88]

    , Macready , W.G

    barticle Wolpert , D.H. , Macready , W.G. : No free lunch theorems for optimization . IEEE transactions on evolutionary computation 1 ( 1 ), 67 -- 82 ( 1997 ) barticle

    1997

  81. [89]

    , Cheng , H

    barticle Xu , Y. , Cheng , H. , Xu , N. , Chen , Y. , Xie , C. : A distribution evolutionary algorithm for the graph coloring problem . Swarm and Evolutionary Computation 80 , 101324 ( 2023 ) 10.1016/j.swevo.2023.101324 barticle

    2023

  82. [90]

    , He , X

    barticle Yang , X.-S. , He , X. : Bat algorithm: literature review and applications . International Journal of Bio-inspired computation 5 ( 3 ), 141 -- 149 ( 2013 ) barticle

    2013

  83. [91]

    : Ensemble methods

    botherref Zhou , Z.-H. : Ensemble methods. Combining pattern classifiers. Wiley, Hoboken, 186--229 (2014) botherref

    2014

  84. [92]

    , Ekim , T

    barticle Şeker , O. , Ekim , T. , Taşkın , Z.C. : An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs . European Journal of Operational Research 291 ( 1 ), 67 -- 83 ( 2021 ) 10.1016/j.ejor.2020.09.017 barticle

    2021 doi

  85. [93]

    write newline

    " write newline " cite write " FUNCTION editor.postfix editor num.names #1 > "( )" "( )" if FUNCTION editor.trans.postfix editor num.names #1 > "( )" "( )" if FUNCTION trans.postfix translator num.names #1 > "( )" "( )" if FUNCTION authors.editors.reflist.apa5 'field := 'dot :...

  86. [94]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key keywords month note number organization pages publisher school series title type url volume year eprint archive archivePrefix primaryClass adsurl adsnote version label INTEGERS o...

  87. [95]

    write newline

    " write newline "" before.all 'output.state := FUNCTION if.digit duplicate "0" = swap duplicate "1" = swap duplicate "2" = swap duplicate "3" = swap duplicate "4" = swap duplicate "5" = swap duplicate "6" = swap duplicate "7" = swap duplicate "8" = swap "9" = or or or or or or...

  88. [96]

    , " * write output.state after.block = add.period write newline

    ENTRY address archive author booktitle chapter doi edition editor eid eprint howpublished institution journal key keywords month note number organization pages publisher school series title type url volume year archivePrefix primaryClass adsurl adsnote version label extra.labe...

  89. [97]

    write newline

    " write newline "" before.all 'output.state := FUNCTION add.period duplicate empty 'skip "." * add.blank if FUNCTION if.digit duplicate "0" = swap duplicate "1" = swap duplicate "2" = swap duplicate "3" = swap duplicate "4" = swap duplicate "5" = swap duplicate "6" = swap dupl...

  90. [98]

    write newline

    " write newline "" before.all 'output.state := FUNCTION output.doi doi empty skip "doi:" doi * "" * output if FUNCTION format.archive archivePrefix empty "" archivePrefix ":" * if FUNCTION format.primaryClass primaryClass empty "" " [" primaryClass * "] " * if FUNCTION format....

  91. [99]

    write newline

    " write newline "" before.all 'output.state := FUNCTION string.to.integer 't := t text.length 'k := #1 'char.num := t char.num #1 substring 's := s is.num s "." = or char.num k = not and char.num #1 + 'char.num := while char.num #1 - 'char.num := t #1 char.num substring FUNCTI...

  92. [100]

    write newline

    " write newline "" before.all 'output.state := FUNCTION string.to.integer 't := t text.length 'k := #1 'char.num := t char.num #1 substring 's := s is.num s "." = or char.num k = not and char.num #1 + 'char.num := while char.num #1 - 'char.num := t #1 char.num substring FUNCTI...

  93. [101]

    , " * write output.state after.block = add.period write newline

    ENTRY address archive author booktitle chapter edition editor eprint howpublished institution journal key keywords month note number organization pages publisher school series title type url doi volume year archivePrefix primaryClass eid adsurl adsnote version label INTEGERS o...

  94. [102]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

  95. [103]

    Available from:

    ENTRY address assignee author booktitle chapter cartographer day edition editor howpublished institution inventor journal key keywords month note number organization pages part publisher school series title type volume word year eprint doi url lastchecked updated archive archi...

  96. [104]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.