Algorithmica, 2016 This paper is devoted to the online dominating set problem and its variants on trees, bipartite, bounded-degree, planar, and general graphs, distinguishing between connected and not necessarily connected graphs. We believe this paper represents the first
Boyar, Joan +4 more
core +9 more sources
Node Deployment Algorithm for Underwater Sensor Networks Based on Connected Dominating Set. [PDF]
Sensors (Basel), 2016 Existing node deployment algorithms for underwater sensor networks are nearly unable to improve the network coverage rate under the premise of ensuring the full network connectivity and do not optimize the communication and move energy consumption during
Jiang P, Liu J, Wu F, Wang J, Xue A.
europepmc +2 more sources
Distributed Dominating Set Approximations beyond Planar Graphs [PDF]
ACM Trans. Algorithms, 2019 The Minimum Dominating Set (MDS) problem is one of the most fundamental and challenging problems in distributed computing. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, there ...
Amiri, Saeed Akhoondian +2 more
core +2 more sources
DEADS: Depth and Energy Aware Dominating Set Based Algorithm for Cooperative Routing along with Sink Mobility in Underwater WSNs. [PDF]
Sensors (Basel), 2015 Performance enhancement of Underwater Wireless Sensor Networks (UWSNs) in terms of throughput maximization, energy conservation and Bit Error Rate (BER) minimization is a potential research area.
Umar A +6 more
europepmc +2 more sources
The Constant Inapproximability of the Parameterized Dominating Set Problem [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2015 We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT= W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem.
Chen, Yijia, Lin, Bingkai
core +3 more sources
Dominating Set Algorithms for Wireless Sensor Networks Survivability
IEEE Access, 2018 Limited energy of the sensors is one of the key issues towards realizing a reliable wireless sensor network (WSN), which can survive under the emerging WSN applications.
Tayler Pino +2 more
doaj +2 more sources
A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems [PDF]
arXiv.org, 2022 A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph.
N. Bousquet +3 more
semanticscholar +1 more source
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation [PDF]
International/Italian Conference on Algorithms and Complexity, 2021 An upper dominating set is a minimal dominating set in a graph. In the Upper Dominating Set problem, the goal is to find an upper dominating set of maximum size. We study the complexity of parameterized algorithms for Upper Dominating Set, as well as its
L. Dublois, M. Lampis, V. Paschos
semanticscholar +1 more source
Efficient Domination In Fuzzy Graphs and Intuitionistic Fuzzy Graphs in Strong and weak forms [PDF]
E3S Web of Conferences, 2023 This work defines the concepts of strong efficient dominating set and intuitionistic fuzzy graph. We also introduce an intuitionistic fuzzy graph and a strong efficient dominating number of fuzzy graphs.
S Rajeev Gandhi +4 more
doaj +1 more source
On minimum intersections of certain secondary dominating sets in graphs [PDF]
Opuscula Mathematica, 2023 In this paper we consider secondary dominating sets, also named as \((1,k)\)-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the \((1,1)\)-dominating sets and proper \((1,2)\)-dominating sets.
Anna Kosiorowska +2 more
doaj +1 more source