Roman domination in subgraphs of grids

DOI10.1016/J.ENDM.2015.07.014zbMath1347.05147OpenAlexW2220850808MaRDI QIDQ324726

Samuel Nascimento, Rudini Menezes Sampaio

Publication date: 17 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.014

zbMATH Keywords

gridRoman dominationAPX-hardfixed parameter tractable

Mathematics Subject Classification ID

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 (2)

On the computational complexity of Roman\(\{2\}\)-domination in grid graphs ⋮ Roman domination and independent Roman domination on graphs with maximum degree three

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for Roman domination on some classes of graphs
• Unit disk graphs
• A partial k-arboretum of graphs with bounded treewidth
• Roman domination in graphs.
• Diameter and treewidth in minor-closed graph families
• Inclusion/exclusion meets measure and conquer
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• The Complexity of Multiterminal Cuts
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†

This page was built for publication: Roman domination in subgraphs of grids