Double vertex-edge domination in graphs: complexity and algorithms

DOI10.1007/S12190-020-01433-5MaRDI QIDQ2053214zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 29 November 2021

Published in Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s12190-020-01433-5

zbMATH Keywords

dominationdouble vertex-edge dominationNP-completepolynomial time algorithmvertex-edge domination

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) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the algorithmic complexity of double vertex-edge domination in graphs
• scientific article; zbMATH DE number 7481760
• scientific article; zbMATH DE number 1843906
• Total vertex-edge domination in graphs: Complexity and algorithms
• On Double Domination in Graphs
• Double vertex-edge domination
• Exact double domination in graphs
• A realization algorithm for double domination in graphs
• scientific article; zbMATH DE number 1792607
• Double total domination of graphs

Cites work

• \(k\)-tuple domination in graphs
• A linear time recognition algorithm for proper interval graphs
• Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs
• Algorithmic aspects of Roman domination in graphs
• Bounds on the vertex-edge domination number of a tree
• Double vertex-edge domination
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• scientific article; zbMATH DE number 4152428 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• Incidence matrices and interval graphs
• On vertex-edge and independent vertex-edge domination
• Optimization, approximation, and complexity classes
• Perfect Roman domination in graphs
• Vertex-edge domination in graphs
• Vertex-edge domination in graphs
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(15)

• An \(O(| V|^*| E|)\) algorithm for finding immediate multiple-vertex dominators
• Nearly tight approximation algorithm for (connected) Roman dominating set
• Polynomial time algorithm for k-vertex-edge dominating problem in interval graphs
• scientific article; zbMATH DE number 1843906 (Why is no real title available?)
• scientific article; zbMATH DE number 7481760 (Why is no real title available?)
• Total vertex-edge domination in graphs: Complexity and algorithms
• On the algorithmic complexity of double vertex-edge domination in graphs
• Double vertex-edge domination
• Vertex-edge domination in unit disk graphs
• Domination number based on fuzzy bridge and application
• On \(k\)-vertex-edge domination of graph
• Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs
• Algorithmic aspects of vertex-edge domination in some graphs.
• Algorithmic study on liar's vertex-edge domination problem
• Approximation algorithm for connected Roman k-dominating set

This page was built for publication: Double vertex-edge domination in graphs: complexity and algorithms

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