Approximation algorithms for the total dominating set problem

DOI10.1007/S10878-025-01311-5MaRDI QIDQ6956318zbMATH OpenFDO

Authors Limin Wang, Zhao Zhang, Donglei Du, Yaping Mao, Xiaoyan Zhang

Publication date 18 July 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-025-01311-5

zbMATH Keywords

approximation algorithmdistributedrounding algorithmtotal dominating set

Mathematics Subject Classification ID

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

Cites work

• A survey of selected recent results on total domination in graphs
• A Transition from Total Domination in Graphs to Transversals in Hypergraphs
• An efficient distributed algorithm for constructing small dominating sets
• An improved exact algorithm for minimum dominating set in chordal graphs
• Approximation algorithms for connected dominating sets
• Approximation hardness of dominating set problems in bounded degree graphs
• Constant-time distributed dominating set approximation
• Domination in Graphs Applied to Electric Power Networks
• Efficient self-stabilizing algorithms for minimal total \(k\)-dominating sets in graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• On the Algorithmic Complexity of Total Domination
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Total domination in graphs
• Total domination in graphs
• Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions

This page was built for publication: Approximation algorithms for the total dominating set problem

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