Double vertex-edge domination in graphs: complexity and algorithms

DOI10.1007/s12190-020-01433-5zbMath1475.05134OpenAlexW3085378289MaRDI QIDQ2053214

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

polynomial time algorithmNP-completedominationvertex-edge dominationdouble vertex-edge domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On \(k\)-vertex-edge domination of graph ⋮ Unnamed Item ⋮ Nearly tight approximation algorithm for (connected) Roman dominating set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(k\)-tuple domination in graphs
• A linear time recognition algorithm for proper interval graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Optimization, approximation, and complexity classes
• Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs
• Algorithmic aspects of Roman domination in graphs
• On vertex-edge and independent vertex-edge domination
• Perfect Roman domination in graphs
• Incidence matrices and interval graphs
• Bounds on the vertex-edge domination number of a tree
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Double vertex-edge domination
• Vertex-edge domination in graphs
• Vertex-edge domination in graphs