Enumerating minimal defensive alliances

DOI10.1016/J.DAM.2025.12.066MaRDI QIDQ6848828zbMATH OpenFDO

Authors Zhidan Feng, Henning Fernau, Kevin Mann

Publication date 5 March 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.12.066

zbMATH Keywords

defensive allianceenumerationglobal minimumlocal minimum

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• A survey on alliances and related parameters in graphs
• A theory of diagnosis from first principles
• A variant of Reiter's hitting-set algorithm
• Algorithmic meta-theorems for restrictions of treewidth
• Alliances in graphs of bounded clique-width
• Alliances in graphs: parameters, properties and applications -- a survey
• Aspects of upper defensive alliances
• Below all subsets for minimal connected dominating set
• Combinatorial bounds via measure and conquer
• Counting minimal dominating sets
• Defensive alliances in graphs
• Defensive alliances in graphs of bounded treewidth
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Enumerating minimal connected dominating sets
• Enumerating minimal dominating sets in chordal graphs
• Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
• Enumeration of minimal connected dominating sets for chordal graphs
• Generating dual-bounded hypergraphs
• Globally minimal defensive alliances
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• scientific article; zbMATH DE number 152108 (Why is no real title available?)
• scientific article; zbMATH DE number 1354130 (Why is no real title available?)
• scientific article; zbMATH DE number 1149451 (Why is no real title available?)
• scientific article; zbMATH DE number 2076807 (Why is no real title available?)
• scientific article; zbMATH DE number 6843424 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Minimal Roman dominating functions: extensions and enumeration
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On cliques in graphs
• On the complexity of solution extension of optimization problems
• On the enumeration of minimal dominating sets and related notions
• Parameterized complexity of locally minimal defensive alliances
• Perfect Roman domination: aspects of enumeration and parameterization
• Planar Formulae and Their Uses
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Proximity Search for Maximal Subgraph Enumeration
• Roman census: enumerating and counting Roman dominating functions on graph classes
• Structures of domination in graphs
• The algorithmic complexity of alliances in graphs
• The complexity of dependency detection and discovery in relational databases
• The maximum number of minimal dominating sets in a tree

This page was built for publication: Enumerating minimal defensive alliances

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