Pith. sign in

REVIEW 3 major objections 5 minor 49 references

The connected Grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper introduces the first exact and heuristic optimization methods for the connected Grundy coloring problem, with a representative-based integer program that dominates the standard one and a local-search genetic algorithm that…

desk verdict A solid, honest first computational treatment of connected Grundy coloring: first IP formulations and a useful BRKGA, with a benchmark-modification caveat that is real but not disqualifying. read the letter →

arxiv 2411.14533 v1 pith:ENXECJEQ submitted 2024-11-21 math.OC cs.DM

Mateus C. Silva , Rafael A. Melo , Mauricio G. C. Resende , Marcio C. Santos , Rodrigo F. Toso This is my paper · ORCID
classification math.OCcs.DM MSC 05C1590C2790C1090C59
keywords connectedGrundycoloringnumberfirst-fitintegerprogrammingformulationbyrepresentativesbiasedrandom-keygeneticalgorithmlocalsearchgraph
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

The paper's goal is to give the first general optimization methods for the connected Grundy coloring problem, in which vertices are colored by a first-fit heuristic over a connected ordering and one wants the maximum number of colors, the connected Grundy number $\Gamma_c(G)$. It proposes two integer programming formulations, a standard partition model and a symmetry-breaking "representatives" model, plus a biased random-key genetic algorithm enhanced with reset and local search. The computational evidence is that the representative formulation wins on small graphs, while the genetic algorithm delivers high-quality colorings on instances up to 500 vertices in five-minute runs. The paper also shows the same local-search framework improves existing heuristic results for the ordinary Grundy coloring problem.

What carries the argument

The central object is a connected Grundy coloring: a proper vertex coloring obtainable by the first-fit rule on a vertex sequence in which every new vertex is adjacent to an earlier one. The argument runs through two IP models; the standard model uses variables $z_{vkt}$ deciding that vertex $v$ receives color $k$ at time $t$, with constraints enforcing properness, the Grundy property, and connectivity, while the representatives model uses variables $Z_{vut}$ and $y_{vu}$ so each vertex is represented by an earlier vertex and representatives are ordered, breaking symmetry. The heuristic machinery is a BRKGA whose random-key vector encodes vertex priorities, a decoder that produces a connected sequence with a priority queue in $O(|V|\log|V| + |E|)$, and a local search that moves a single vertex to a position next to one of its neighbors; Propositions 7 and 8 give $O(1)$ and $O(|N(v)|)$ connectivity checks that make the neighborhood search practical.

What would settle it

Take a small disconnected graph with three components, compute the connected Grundy number of the path-connected version produced by the Section 5.1.1 procedure, and compare it with the maximum connected Grundy number of the components; the first non-trivial case where the two differ shows that the benchmark modification changes the problem being solved.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that connected Grundy coloring can be attacked directly: the first claim is that two integer programming formulations correctly encode first-fit colorings over connected vertex sequences, with the representatives model breaking symmetries, and that the representatives model is computationally superior on the tested benchmark. The second claim is that a biased random-key genetic algorithm whose decoder builds a connected sequence by repeatedly extracting the highest-priority reachable vertex, with a local search that moves one vertex next to a neighbor and a reset mechanism, reliably produces high-quality colorings for instances up to 500 vertices. The paper further reports that the approach, with connectivity checks removed, improves the Grundy coloring problem, finding new best-known solutions on 36 of 362 benchmark instances.

Load-bearing premise

The load-bearing premise is that adding a path between the highest-degree vertices of disconnected components leaves the connected Grundy number unchanged in the typical case; the paper itself gives a graph with two isolated vertices where this fails, so the modified benchmark results may not transfer to the original disconnected graphs.

Editorial extensions

If this is right

  • Exact computation of the connected Grundy number is feasible for small graphs: the two formulations together proved optimality on 132 of 240 instances with up to 30 vertices, and another 46 were certified optimal by matching known upper bounds.
  • The symmetry-breaking representatives formulation is the stronger exact tool, especially on dense instances, and is the better starting point for any future exact method.
  • The reset-and-local-search BRKGA recipe transfers to the ordinary Grundy coloring problem, where it produced new best-known solutions on 36 of 362 instances.
  • Large graphs of up to 500 vertices can receive good connected Grundy colorings within a 300-second budget, making the heuristic usable where the IPs run out of memory.
  • Because $\Gamma_c(G) \le \Gamma(G)$, any connected coloring that reaches a known Grundy upper bound is automatically optimal; this certificate was used throughout the small-instance experiments.

Reading between the lines

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

  • The benchmark-connection procedure in Section 5.1.1 is the paper's least controlled step: if adding a path between high-degree vertices changes the connected Grundy number for graphs beyond the two-isolated-vertices example, the large-instance results describe the modified graphs rather than the original disconnected benchmarks.
  • The representatives model's edge on dense graphs suggests that symmetry is the principal obstacle for exact connected Grundy coloring, so symmetry-breaking cuts or orbitopal fixing could plausibly extend exact solvability beyond 30 vertices.
  • The move-one-vertex-next-to-a-neighbor neighborhood is a generic operation for first-fit-based coloring problems and could be tested on connected greedy edge colorings or other constrained first-fit settings.
  • The paper does not explore incremental decoding, but the decoder's priority-queue structure suggests the BRKGA could be adapted to streaming graphs where vertices arrive over time.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies the connected Grundy coloring problem, in which one seeks a proper vertex coloring obtainable by a first-fit heuristic on a connected vertex sequence, maximizing the number of colors. The authors propose two integer programming formulations (a standard partition-based model and a representatives-based model), and a biased random-key genetic algorithm (BRKGA) enhanced with a reset mechanism and a local search procedure using a newly defined neighborhood. They provide a theoretical analysis of the local search neighborhood, present computational experiments on instances with up to 30 vertices for the exact methods and up to 500 vertices for the heuristics, and extend the approach to the (non-connected) Grundy coloring problem.

Significance. If the results are correct, this is the first systematic optimization study of the connected Grundy coloring problem, a natural NP-hard variant of Grundy coloring. The two IP formulations are non-trivial, and the neighborhood analysis is a useful theoretical contribution. The paper also shows that the proposed BRKGA can be adapted to the Grundy coloring problem and may improve known results. The computational study is extensive, with 50 runs per instance and comparisons across several graph classes. However, the empirical support for the central claim is weakened by an unproven modification of disconnected benchmark instances, and the correctness of the formulations is asserted rather than formally proven. The local-search theory also contains a proof gap that should be addressed.

major comments (3)
  1. [5.1.1] The procedure that connects disconnected benchmark instances by adding a path between the highest-degree vertices of each component can change the connected Grundy number of the resulting graph; the authors themselves concede the counterexample of two isolated vertices, where the optimum increases from 1 to 2. The paper neither reports how many of the 282 tested instances were disconnected nor provides any empirical or theoretical validation that the equality Γc(G) = max_i Γc(G_i) holds for the instances actually used in Tables 7-10. Since the BRKGA objective values are computed on these modified graphs, the reported solution qualities cannot be directly attributed to the original benchmark graphs. This weakens the central claim that the proposed BRKGA finds high-quality solutions on the original instance set. The authors should restrict the benchmark to connected graphs, or prove invariance conditions for their modification, or report per-instance evidence that the modification does not alter the optimum (for example, using the combinatorial upper bounds on the original components).
  2. [2] The paper does not provide a formal proof that formulations (1)-(9) and (10)-(20) are exact models of the connected Grundy coloring problem. In particular, the representatives-based formulation contains subtle constraints such as (12), (14), and (15) whose interpretation is not fully formalized, and it is not shown that the integer programming optimum equals Γc(G) for every connected graph G. A correctness proof, or at least a detailed bijection between feasible IP solutions and connected Grundy colorings, is essential because the optimality claims in Section 5.3 and the use of these formulations as exact benchmarks depend on this equivalence.
  3. [4.2] The proof of Proposition 4 is not rigorous as written. In the case p_S'(v) < p_S(v), the interval [1, p_S'(v)] in S' contains the vertex v, whereas in S it contains the vertex that occupied that position before the move, so the statement that the two solutions have the same vertices colored the same way in that interval is false. The conclusion that all vertices keep their colors may still be true, but the proof must be corrected; as written, it does not rule out the possibility that a vertex adjacent to v changes color because v now appears earlier with the same color. Since Proposition 4 is used to justify pruning in the local search (Section 4.3), a correct proof is needed.
minor comments (5)
  1. [3.2] In Algorithm 1, line 10, the pseudocode enqueues the variable v (the vertex just colored) instead of u (the neighbor being examined); it should read Enqueue(Q, u).
  2. [4] The first paragraph of Section 4 contains a typo: 'in it's i-th position' should be 'in its i-th position'. The abstract also has 'AGrundy' missing a space.
  3. [6.1] The caption of Figure 11(a) refers to 'BRKGA+R+LS and BRKGA-B', but the comparison is with BRKGA-G (the Grundy coloring BRKGA from Silva et al.); the caption should be corrected.
  4. [5.2] The parameter tuning is performed on a subset of 28 instances; the paper should clarify whether these instances are also included in the final test set, since in-sample tuning would make the reported differences more favorable to the tuned variant.
  5. [5.4] Tables 7-10 report averages over 50 runs but no dispersion measure; adding standard deviations or confidence intervals would help the reader judge the variability of the reported improvements.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the IP formulations and decoder are derived from the problem definition, and the prior-work upper bound and BRKGA baselines are used as independent benchmarks, not as fitted targets.

full rationale

The paper's central mathematical content is self-contained. The standard and representative IP formulations directly encode the connected first-fit and connectivity conditions (constraints (5) and (7) in the standard model; (14) and (15) in the representatives model), and the decoder in Algorithm 1 constructs a connected sequence by a priority queue, so its output is a connected Grundy coloring by construction rather than by calibration. The upper bounds ζ(G), Δ2(G)+1, and Ψ(G) used to truncate the color set are cited mathematical bounds; Ψ(G) comes from the authors' earlier Silva et al. (2024) paper, but it is a parameter-free proven inequality, not a value fitted in this paper, so invoking it does not make the present claims circular. The comparisons with BRKGA-B and with Silva et al.'s BRKGA-G are external benchmark comparisons: BRKGA-G is an independently reported algorithm, and BRKGA-B is a controlled ablation, not a fitted predictor of the results being claimed. Hyperparameter selection on a disclosed 28-instance subset is standard practice and does not reduce any reported solution value to a fit. The one substantive weakness is Section 5.1.1, where disconnected benchmark instances are modified by adding paths between components; the authors explicitly concede a case in which the connected Grundy number changes (two isolated vertices). This is a benchmark-validity caveat: the modified instances are different inputs, so performance on them may not transfer to the original graphs. It does not, however, make any derivation equivalent to its inputs, and no equation or heuristic output is forced by a fitted parameter. Hence no circularity is present.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are introduced. The free parameter is the BRKGA hyperparameter set, tuned on a subset of instances. The main axioms are the validity of known upper bounds, the correctness of the time-indexed IP encoding, and a heuristic graph-connection assumption that is admitted to have exceptions.

free parameters (1)
  • BRKGA population and genetic parameters = p=1.7*|V| for BRKGA+R+LS, pe=30%, pm=10%, rho_e=60%, glim=2000, local search on 5 solutions
    Selected via grid search on a subset of 28 instances (Section 5.2). The performance claims of the BRKGA depend on these settings, and different settings could change the outcomes.
assumptions (4)
  • domain assumption Validity of combinatorial upper bounds ζ(G), Δ2(G)+1, Ψ(G) for the Grundy number
    Used to limit the set of colors K in both IP formulations (Section 2). If any bound were invalid, the formulations could exclude optimal colorings. Ψ(G) is from the authors' previous paper Silva et al. (2024).
  • domain assumption Correctness of the time-indexed encoding of first-fit sequences
    The IP constraints (5) and (14) assume that a vertex colored at time t can only use colors present among neighbors colored before t, which correctly models the first-fit heuristic on a connected sequence. This is asserted textually rather than formally proved.
  • ad hoc to paper The connected-sequence modification of disconnected benchmark graphs preserves the connected Grundy number in most cases
    Section 5.1.1 adds paths between components and asserts Γc(G)=max Γc of components for most cases, but gives a counterexample with two isolated vertices where the equality fails. This is an unproven heuristic that affects benchmark validity.
  • standard math Standard graph theory definitions and NP-hardness of connected Grundy coloring from Benevides et al. (2014)
    Background results relied upon for problem definition and complexity context.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The connected Grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm." pith.science (2026). https://pith.science/paper/ENXECJEQ

@misc{pith2026241114533,
  author       = {Pith},
  title        = {Pith review of: The connected Grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ENXECJEQ}},
  note         = {Machine review of arXiv:2411.14533}
}
read the original abstract

Given a graph G=(V,E), a connected Grundy coloring is a proper vertex coloring that can be obtained by a first-fit heuristic on a connected vertex sequence. A first-fit coloring heuristic is one that attributes to each vertex in a sequence the lowest-index color not used for its preceding neighbors. A connected vertex sequence is one in which each element, except for the first one, is connected to at least one element preceding it. The connected Grundy coloring problem consists of obtaining a connected Grundy coloring maximizing the number of colors. In this paper, we propose two integer programming (IP) formulations and a local-search enhanced biased random-key genetic algorithm (BRKGA) for the connected Grundy coloring problem. The first formulation follows the standard way of partitioning the vertices into color classes while the second one relies on the idea of representatives in an attempt to break symmetries. The BRKGA encompasses a local search procedure using a newly proposed neighborhood. A theoretical neighborhood analysis is also presented. Extensive computational experiments indicate that the problem is computationally demanding for the proposed IP formulations. Nonetheless, the formulation by representatives outperforms the standard one for the considered benchmark instances. Additionally, our BRKGA can find high-quality solutions in low computational times for considerably large instances, showing improved performance when enhanced with local search and a reset mechanism. Moreover we show that our BRKGA can be easily extended to successfully tackle the Grundy coloring problem, i.e., the one without the connectivity requirements.

Figures

Figures reproduced from arXiv: 2411.14533 by the authors.

Figure 1
Figure 1. Difference in the resulting colorings when using a non-connected and a connected sequence [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Coloring of a graph corresponding to the solution with the only non-zero values [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Framework of the BRKGA enhanced with local search. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Population evolution between two generations of a BRKGA. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Example of a random-key vector and the connected sequence generated by the decoder. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Example of the solutions obtained by applying a move operation on vertex [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Example of how moving a vertex can lead to changing the color of all vertices. [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]
Figure 8
Figure 8. Figure 8: Connecting two components using the highest degree vertex of each component, with the [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: Boxplot of the percentage deviation of the average number of colors found by the [PITH_FULL_IMAGE:figures/full_fig_p021_9.png]
Figure 10
Figure 10. Figure 10: Boxplots comparing the percentage deviations between BRKGA+R+LS and BRKGA-B. [PITH_FULL_IMAGE:figures/full_fig_p022_10.png]
Figure 11
Figure 11. Figure 11: Boxplots comparing the percentage deviations between BRKGA+R+LS and BRKGA-G [PITH_FULL_IMAGE:figures/full_fig_p025_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

  1. [1]

    Avanthay, A

    C. Avanthay, A. Hertz, and N. Zufferey. A variable neighborhood search for graph coloring. European Journal of Operational Research, 151 0 (2): 0 379--388, 2003

    work page 2003

  2. [2]

    Bahiense, Y

    L. Bahiense, Y. A. M. Frota, T. F. Noronha, and C. C. Ribeiro. A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives. Discrete Applied Mathematics, 164: 0 34--46, 2014

    work page 2014

  3. [3]

    J. C. Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6 0 (2): 0 154--160, 1994

    work page 1994

  4. [4]

    Benevides, V

    F. Benevides, V. Campos, M. Dourado, S. Griffiths, R. Morris, L. Sampaio, and A. Silva. Connected greedy colourings. In Latin A merican S ymposium on T heoretical I nformatics , pages 433--441. Springer, 2014

    work page 2014

  5. [5]

    C. Berge. Graphs and hypergraphs. North-Holland Publishing Co., 1973

    work page 1973

  6. [6]

    Bonamy, C

    M. Bonamy, C. Groenland, C. Muller, J. Narboni, J. Pek \'a rek, and A. Wesolek. A note on connected greedy edge colouring. Discrete Applied Mathematics, 304: 0 129--136, 2021

    work page 2021

  7. [7]

    Bonnet, F

    \'E . Bonnet, F. Foucaud, E. J. Kim, and F. Sikora. Complexity of G rundy coloring and its variants. Discrete Applied Mathematics, 243: 0 99--114, 2018

    work page 2018

  8. [8]

    Br \'e laz

    D. Br \'e laz. New methods to color the vertices of a graph. Communications of the ACM, 22 0 (4): 0 251--256, 1979

    work page 1979

Show all 49 references
  1. [9]

    Camp\^elo, V

    M. Camp\^elo, V. Campos, and R. Corr\^ea. On the asymmetric representatives formulation for the vertex coloring problem. Electronic Notes in Discrete Mathematics, 19: 0 337--343, 2005

    2005

  2. [10]

    C. A. Christen and S. M. Selkow. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27 0 (1): 0 49--59, 1979

    1979

  3. [11]

    R. C. Corr\^ea, M. Camp\^elo, and Y. A. M. Frota. Cliques, holes and the vertex coloring polytope. Information Processing Letters, 89: 0 159--164, 2004

    2004

  4. [12]

    de Freitas, B

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

    2021

  5. [13]

    Erd o s, W

    P. Erd o s, W. Hare, S. T. Hedetniemi, and R. Laskar. On the equality of the G rundy and ochromatic numbers of a graph. Journal of Graph Theory, 11 0 (2): 0 157--159, 1987

    1987

  6. [14]

    Frota, N

    Y. Frota, N. Maculan, T. F. Noronha, and C. C. Ribeiro. A branch-and-cut algorithm for partition coloring. Networks: An International Journal, 55: 0 194--204, 2010

    2010

  7. [15]

    Furini, E

    F. Furini, E. Malaguti, and A. Santini. An exact algorithm for the partition coloring problem. Computers & Operations Research, 92: 0 170--181, 2018

    2018

  8. [16]

    J. F. Gon c alves and M. G. Resende. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17 0 (5): 0 487--525, 2011

    2011

  9. [17]

    J. F. Gon c alves and G. W \"a scher. A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects. European Journal of Operational Research, 286 0 (3): 0 867--882, 2020

    2020

  10. [18]

    P. M. Grundy. Mathematics and games. Eureka, 2: 0 6--9, 1939

    1939

  11. [19]

    Y. He, C. Gao, N. Sang, Z. Qu, and J. Han. Graph coloring based surveillance video synopsis. Neurocomputing, 225: 0 64--79, 2017

    2017

  12. [20]

    S. M. Hedetniemi, S. T. Hedetniemi, and T. Beyer. A linear algorithm for the grundy (coloring) number of a tree. Congressus Numerantium, 36: 0 351--363, 1982

    1982

  13. [21]

    S. M. Homayouni, D. B. Fontes, and J. F. Gon c alves. A multistart biased random key genetic algorithm for the flexible job shop scheduling problem with transportation. International Transactions in Operational Research, 30 0 (2): 0 688--716, 2023

    2023

  14. [22]

    D. S. Johnson, L. Breslau, I. Diakonikolas, N. Duffield, Y. Gu, M. Hajiaghayi, H. Karloff, M. G. C. Resende, and S. Sen. Near-optimal disjoint-path facility location through set cover by pairs. Operations Research, 68: 0 896--926, 2020

    2020

  15. [23]

    Jovanovi \'c , N

    P. Jovanovi \'c , N. Pavlovi \'c , I. Belo s evi \'c , and S. Milinkovi \'c . Graph coloring-based approach for railway station design analysis and capacity determination. European Journal of Operational Research, 287 0 (1): 0 348--360, 2020

    2020

  16. [24]

    M. A. Londe, L. S. Pessoa, C. E. Andrade, and M. G. C. Resende. Early years of biased random-key genetic algorithms: A systematic review. Journal of Global Optimization, 2024. URL https://doi.org/10.1007/s10898-024-01446-5

    2024 doi

  17. [25]

    M. A. Londe, L. S. Pessoa, C. E. Andrade, and M. G. C. Resende. Biased random-key genetic algorithms: A review. European Journal of Operational Research, 321 0 (1): 0 1--22, 2025

    2025

  18. [26]

    L \"u and J.-K

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

    2010

  19. [27]

    R. G. Marzo, R. A. Melo, C. C. Ribeiro, and M. C. Santos. New formulations and branch-and-cut procedures for the longest induced path problem. Computers & Operations Research, 139: 0 105627, 2022

    2022

  20. [28]

    R. A. Melo and C. C. Ribeiro. Improved solutions for the freight consolidation and containerization problem using aggregation and symmetry breaking. Computers & Industrial Engineering, 85: 0 402--413, 2015

    2015

  21. [29]

    R. A. Melo and C. C. Ribeiro. MIP formulations for induced graph optimization problems: a tutorial. International Transactions in Operational Research, 30 0 (6): 0 3159--3200, 2023

    2023

  22. [30]

    R. A. Melo, M. F. Queiroz, and M. C. Santos. A matheuristic approach for the b -coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic. European Journal of Operational Research, 295 0 (1): 0 66--81, 2021

    2021

  23. [31]

    R. A. Melo, C. C. Ribeiro, and J. A. Riveaux. The minimum quasi-clique partitioning problem: Complexity, formulations, and a computational study. Information Sciences, 612: 0 655--674, 2022

    2022

  24. [32]

    R. A. Melo, C. C. Ribeiro, and J. A. Riveaux. A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem. Annals of Operations Research, 2023. doi:10.1007/s10479-023-05609-7

    2023 doi

  25. [33]

    Moalic and A

    L. Moalic and A. Gondran. Variations on memetic algorithms for graph coloring problems. Journal of Heuristics, 24 0 (1): 0 1--24, 2018

    2018

  26. [34]

    Morgenstern

    C. Morgenstern. Graph generator ggen, 2015. Online reference at http://iridia.ulb.ac.be/ fmascia/files/ggen.tar.bz2, last accessed on July 25, 2023

    2015

  27. [35]

    E. Mota, L. Rocha, and A. Silva. Connected greedy coloring of H -free graphs. Discrete Applied Mathematics, 284: 0 572--584, 2020

    2020

  28. [36]

    Nogueira, R

    B. Nogueira, R. G. Pinheiro, and A. Subramanian. A hybrid iterated local search heuristic for the maximum weight independent set problem. Optimization Letters, 12 0 (3): 0 567--583, 2018

    2018

  29. [37]

    M. G. C. Resende, R. F. Toso, J. F. Gonçalves, and R. M. A. Silva. A biased random-key genetic algorithm for the steiner triple covering problem. Optimization Letters, 6 0 (4): 0 605--619, 2012

    2012

  30. [38]

    San Segundo, S

    P. San Segundo, S. Coniglio, F. Furini, and I. Ljubi \'c . A new branch-and-bound algorithm for the maximum edge-weighted clique problem. European Journal of Operational Research, 278 0 (1): 0 76--90, 2019

    2019

  31. [39]

    Z. Shi, W. Goddard, S. T. Hedetniemi, K. Kennedy, R. Laskar, and A. McRae. An algorithm for partial grundy number on trees. Discrete Mathematics, 304 0 (1-3): 0 108--116, 2005

    2005

  32. [40]

    M. C. Silva, R. A. Melo, M. C. Santos, R. F. Toso, and M. G. C. Resende. Obtaining the G rundy chromatic number: How bad can my greedy heuristic coloring be? Computers & Operations Research, 168: 0 106703, 2024

    2024

  33. [41]

    S. E. Silva, C. C. Ribeiro, and U. dos Santos Souza. A biased random-key genetic algorithm for the chordal completion problem. RAIRO-Operations Research, 57 0 (3): 0 1559--1578, 2023

    2023

  34. [42]

    G. J. Simmons. On the ochromatic number of a graph. Congressus Numerantium, 40: 0 339--366, 1983

    1983

  35. [43]

    Spears and K

    W. Spears and K. A. De Jong . On the virtues of parameterized uniform crossover. In R. Belew and L. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms, pages 230--236, San Mateo, 1991. Morgan Kaufman

    1991

  36. [44]

    J. A. Telle and A. Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10 0 (4): 0 529--550, 1997

    1997

  37. [45]

    R. F. Toso. API for biased random-key genetic algorithms, 2018. Online reference at https://github.com/rfrancotoso/brkgaAPI, last accessed on December 5, 2022

    2018

  38. [46]

    R. F. Toso and M. G. Resende. A C++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30 0 (1): 0 81--93, 2015

    2015

  39. [47]

    Trick, V

    M. Trick, V. Chvatal, B. Cook, D. Johnson, C. McGeoch, and B. Tarjan. Benchmark instances from the S econd DIMACS I mplementation C hallenge, 2015. Online reference at http://archive.dimacs.rutgers.edu/pub/challenge/graph/benchmarks/, last access on July 25, 2023

    2015

  40. [48]

    M. Zaker. New bounds for the chromatic number of graphs. Journal of Graph Theory, 58 0 (2): 0 110--122, 2008

    2008

  41. [49]

    X. Zhu, L. Dai, and Z. Wang. Graph coloring based pilot allocation to mitigate pilot contamination for multi-cell massive MIMO systems. IEEE Communications Letters, 19 0 (10): 0 1842--1845, 2015

    2015

Pith tools

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