Minimal Roman dominating functions: extensions and enumeration

DOI10.1007/978-3-031-15914-5_1MaRDI QIDQ6043174zbMATH OpenOpenAlexFDO

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

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.04765

zbMATH Keywords

enumerationextension problemsRoman domination

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves differently in two aspects: enumeration and extension. We develop non-trivial enumeration algorithms for minimal Roman domination functions with polynomial delay and polynomial space. Recall that the existence of a similar enumeration result for minimal dominating sets is open for decades. Our result is based on a polynomial-time algorithm for Extension Roman Domination: Given a graph $G=(V,E)$ and a function $f:Vo0,1,2$, is there a minimal Roman domination function $Tildef$ with $fleqTildef$? Here, $leq$ lifts $0<1<2$ pointwise; minimality is understood in this order. Our enumeration algorithm is also analyzed from an input-sensitive viewpoint, leading to a run-time estimate of $Oh(RomanUpperboun{d}^n)$ for graphs of order n; this is complemented by a lower bound example of $Omega(RomanLowerboun{d}^n)$.

Recommendations

• Minimum Roman dominating functions: adjacency
• On the enumeration of minimal dominating sets and related notions
• Total Roman \(\{2\}\)-dominating functions in graphs
• On Roman domination number of functigraph and its complement
• Enumeration of minimal dominating sets and variants
• Roman κ-domination revisited
• Extremal problems on weak Roman domination number
• On the total and strong version for Roman dominating functions in graphs
• Algorithmic results in Roman dominating functions on graphs
• Roman \(k\)-domination in graphs

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
• Invited talks
• 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 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

(2)

• Enumerating minimal connected dominating sets
• Perfect Roman domination: aspects of enumeration and parameterization

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 Q6043174)