Algorithmic results in Roman dominating functions on graphs

DOI10.1016/j.ipl.2023.106363OpenAlexW4317929761MaRDI QIDQ6161427

Jafar Fathali, Abolfazl Poureidi

Publication date: 5 June 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2023.106363

zbMATH Keywords

approximation algorithmNP-completeAPX-completeinteger linear programRoman dominating function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

On [ k -Roman domination in graphs]

Cites Work

• Unnamed Item
• Roman domination on strongly chordal graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Efficient algorithms for Roman domination on some classes of graphs
• Optimization, approximation, and complexity classes
• The complexity of domination problems in circle graphs
• Roman domination in graphs.
• Some APX-completeness results for cubic graphs
• Algorithmic aspects of Roman domination in graphs
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Improved mixed integer linear programing formulations for roman domination problem

This page was built for publication: Algorithmic results in Roman dominating functions on graphs