|
|
|
|
|
Salim Bouamama and Christian Blum
This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications...
ver más
|
|
|
|
|
|
|
|
|
|
|
Jonathan Li, Rohan Potru and Farhad Shahrokhi
We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent Linear programming (LP) rounding algorithms and a hybrid algori...
ver más
|
|
|
|
|
|
|
|
|
|
|
Abdel-Rahman Hedar, Shada N. Abdulaziz, Adel A. Sewisy and Gamal A. El-Sayed
An efficient routing using a virtual backbone (VB) network is one of the most significant improvements in the wireless sensor network (WSN). One promising method for selecting this subset of network nodes is by finding the minimum connected dominating se...
ver más
|
|
|
|
|
|
|
|
|
|
|
Jong-Shin Chen, Ruo-Wei Hung, Fatemeh Keshavarz-Kohjerdi and Yung-Fa Huang
Supergrid graphs are derived by computing stitch paths for computerized embroidery machines. In the past, we have studied the Hamiltonian-related properties of supergrid graphs and their subclasses of graphs. In this paper, we propose a generalized graph...
ver más
|
|
|
|
|
|
|
|
|
|
|
Stephen Finbow and Christopher M. van Bommel
For a graph ??=(??,??)
G
=
(
V
,
E
)
, the ??
?
-graph of G, denoted ??(??)=(??(??),??(??))
G
(
?
)
=
(
V
(
?
)
,
E
(
?
)
)
, is the graph whose vertex set is the collection of minimum dominating sets, or ??
?
-sets of G, and two ??
?
-sets are adjacent ...
ver más
|
|
|
|
|
|