Enumerating minimal defensive alliances
Abstract
In this paper, we study the task of enumerating (and counting) locally and globally minimal defensive alliances in graphs. We consider general graphs as well as special graph classes, like trees, bipartite graphs, and split graphs. From an input-sensitive perspective, our presented algorithms are mostly optimal, meaning that their running times (neglecting polynomial factors) match concrete families of graphs that contain that many minimal alliances.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Graph Labeling and Dimension Problems
Publication details
- Journal / source
- Discrete Applied Mathematics
- Volume
- 384
- Pages
- 309–325
- Publication date
- 12 January 2026
- Language
- EN