EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Graph Burning: An Overview of Compact Mathematical Programs

Lourdes Beatriz Cajica-Maceda, Freddy Alejandro Chaurra-Gutiérrez, Julio César Pérez-Sansalvador, Jesús García-Díaz

Mathematics · 17.03.2026 · 14 (6) · 1011

DOI: 10.3390/math14061011 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics, online erschienen am 17.03.2026. Verfasst von Lourdes Beatriz Cajica-Maceda und 3 weiteren Autor:innen. Die Arbeit nennt 60 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Graph Burning Problem (GBP) is a combinatorial optimization problem that has gained relevance as a tool for quantifying a graph’s vulnerability to contagion. Although it is based on a very simple propagation model, its decision version is NP-complete and its optimization version is NP-hard. This paper introduces novel mathematical programs for the GBP. Among the introduced programs are a Mixed-Integer Linear Program (MILP), a Constraint Satisfaction Problem (CSP), two Integer Linear Programs (ILPs), and two Quadratic Unconstrained Binary Optimization (QUBO) problems. Most optimization solvers can handle these, with QUBO problems being of capital interest in quantum computing. Nonetheless, the primary objective of this paper is not to solve instances of the GBP, but rather to deepen our understanding of it by identifying and examining what we believe to be its simplest mathematical formulations, that is, models that use as few variables and constraints as possible (compact mathematical programs). We believe that this collection of programs can provide ideas for modeling variants and related problems. As a marginal result, one of the proposed ILPs, equipped with a row generation technique, allowed a commercial solver to find optimal solutions for some of the largest and most challenging instances for the GBP.

Zitieren

APA

Cajica-Maceda, L. B., Chaurra-Gutiérrez, F. A., Pérez-Sansalvador, J. C., & García-Díaz, J. (2026). Graph Burning: An Overview of Compact Mathematical Programs. Mathematics, 14(6), 1011. https://doi.org/10.3390/math14061011

Vancouver

Cajica-Maceda LB, Chaurra-Gutiérrez FA, Pérez-Sansalvador JC, García-Díaz J. Graph Burning: An Overview of Compact Mathematical Programs. Mathematics. 2026;14(6):1011. doi:10.3390/math14061011

BibTeX
@article{CajicaMaceda2026,
  author = {Cajica-Maceda, Lourdes Beatriz and Chaurra-Gutiérrez, Freddy Alejandro and Pérez-Sansalvador, Julio César and García-Díaz, Jesús},
  title = {Graph Burning: An Overview of Compact Mathematical Programs},
  journal = {Mathematics},
  year = {2026},
  volume = {14},
  number = {6},
  pages = {1011},
  doi = {10.3390/math14061011}
}
Kostenlos starten →