Approximation algorithm for the semitotal domination problem in unit disk graphs

DOI10.1016/J.DAM.2026.05.013MaRDI QIDQ7289246zbMATH OpenFDO

Authors Michael A. Henning, Pawan Kumar Mishra, Kartik Sehgal, Shaurya M. Tripathi, Sridhar Tuli

Publication date 2 July 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.05.013

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites work

• A characterization of graphs with semitotal domination number one-third their order
• A linear-time algorithm for semitotal domination in strongly chordal graphs
• Algorithmic aspects of semitotal domination in graphs
• Domination in Graphs: Core Concepts
• Edge weighting functions on semitotal dominating sets
• Graphs with semitotal domination number half their order
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On matching and semitotal domination in graphs
• Perfect graphs involving semitotal and semipaired domination
• Semi-total domination in unit disk graphs
• Semitotal domination versus domination and total domination in trees
• Semitotal domination in claw-free cubic graphs
• Semitotal domination in graphs
• Semitotal domination in graphs: partition and algorithmic results
• Semitotal domination in trees
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Simple heuristics for unit disk graphs
• The semitotal domination problem in block graphs
• Topics in Domination in Graphs
• Total domination in graphs
• Vertices contained in all or in no minimum semitotal dominating set of a tree

This page was built for publication: Approximation algorithm for the semitotal domination problem in unit disk graphs

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