Minimal Roman dominating functions: extensions and enumeration

DOI10.1007/S00453-024-01211-WMaRDI QIDQ6547209zbMATH OpenFDO

Authors Faisal N. Abu-Khzam, Henning Fernau, Kevin Mann

Publication date 30 May 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-024-01211-W

zbMATH Keywords

enumerationextension problemspolynomial delayRoman domination

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• A note on Roman domination in graphs
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• A Roman domination chain
• Bounds on Roman domination numbers of graphs
• Combinatorics for smaller kernels: the differential of a graph
• Computing the differential of a graph: hardness, approximability and exact algorithms
• Data reductions and combinatorial bounds for improved approximation algorithms
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Differentials in graphs
• Dual subimplicants of positive Boolean functions
• Efficient algorithms for Roman domination on some classes of graphs
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in chordal bipartite graphs
• Enumerating minimal dominating sets in chordal graphs
• Enumerating Minimal Dominating Sets in Triangle-Free Graphs
• Exact Algorithms for Weak Roman Domination
• Extension of some edge graph problems: standard and parameterized complexity
• Extremal problems for roman domination
• Few compare to the great Roman Empire
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On the complexity of solution extension of optimization problems
• On the enumeration of minimal dominating sets and related notions
• On the number of minimal dominating sets on some graph classes
• On the roman domination in the lexicographic product of graphs
• On the Roman domination number of a graph
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• Roman census: enumerating and counting Roman dominating functions on graph classes
• ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
• Roman domination in Cartesian product graphs and strong product graphs
• Roman domination in graphs.
• Roman domination in regular graphs
• Roman domination on 2-connected graphs
• Roman domination on strongly chordal graphs
• The differential and the roman domination number of a graph
• The many facets of upper domination
• The minimal hitting set generation problem: algorithms and computation
• Topics in Domination in Graphs
• Upper bounds on Roman domination numbers of graphs

Cited in

(4)

• Enumerating minimal defensive alliances
• Extension perfect Roman domination
• Roman hitting functions
• Roman census: enumerating and counting Roman dominating functions on graph classes

This page was built for publication: Minimal Roman dominating functions: extensions and enumeration

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