k-Efficient domination: Algorithmic perspective

DOI10.1142/S1793830922500513MaRDI QIDQ6115759zbMATH OpenOpenAlexFDO

Authors Mohsen Alambardar Meybodi

Publication date 13 July 2023

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830922500513

zbMATH Keywords

dominationefficient dominationparametrized complexity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Efficient (j,k)-domination
• Efficient domination and efficient edge domination: a brief survey
• Algorithmic aspects of the \(k\)-domination problem in graphs
• On efficient dominating sets in simplicial graphs
• scientific article; zbMATH DE number 4085682
• Efficient \((j, k)\)-dominating functions
• On the algorithmic complexity of \(k\)-tuple total domination
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Generalized domination and efficient domination in graphs
• Efficient total domination in digraphs

Cites work

• k-efficient partitions of graphs
• Algorithmic aspects of k-part degree restricted domination in graphs
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• Characterisations of nowhere dense graphs (invited talk)
• Complexity of certain functional variants of total domination in chordal bipartite graphs
• Domination problems in nowhere-dense classes of graphs
• Double domination and super domination in trees
• Fixed-Parameter Tractability and Completeness I: Basic Results
• FPT algorithms for domination in biclique-free graphs
• scientific article; zbMATH DE number 4085682 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 975419 (Why is no real title available?)
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• On the domination number of a graph and its total graph
• On the parameterized complexity of multiple-interval graph problems
• Perfect codes in graphs
• The weighted perfect domination problem and its variants
• Total domination in graphs
• Weighted efficient domination problem on some perfect graphs

Cited in

(7)

• An \(O(| V|^*| E|)\) algorithm for finding immediate multiple-vertex dominators
• scientific article; zbMATH DE number 1320677 (Why is no real title available?)
• k-efficient partitions of graphs
• Edge-vertex domination on interval graphs
• On bounds and exact values of k-efficient domination number of a graph
• Optimal vertex set partitions into different closed neighborhoods in powers of graphs and their complements
• Minimum vertex-edge dominating set of permutation graphs

This page was built for publication: k-Efficient domination: Algorithmic perspective

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