Wyniki wyszukiwania - Biblioteka Nauki

1

Connected domination polynomial of graphs

100%

Mojdeh D. A. , Emadi A. S.

Fasciculi Mathematici

|

2018

|

tom Nr 60

103--121

EN

Let G be a simple graph of order n. The connected domination polynomial of G is the polynomial Dc (G, x) = Σ |V(G)| i=γc(G) dc (G, i)xi, where dc (G, i) is the number of connected dominating sets of G of size i and γc (G) is the connected domination number of G. In this paper we study Dc (G, x) of any graph. We classify many families of graphs by studying their connected domination polynomial.

2

A simple linear algorithm for the connected domination problem in circular-arc graphs

100%

Hung R.-W. , Chang M.-S.

Discussiones Mathematicae Graph Theory

|

2004

|

tom 24

|

nr 1

137-145

EN

A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.

3

An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube

88%

Zhang J. , Xu L. , Zhou S.-m. , Wu W. , Ye X.

International Journal of Applied Mathematics and Computer Science

|

2015

|

tom 25

|

nr 2

295-309

EN

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of the crossed cube (ITCC) is presented. The ITCC is to find a maximal independent set (MIS), which is based on building an induced tree of the crossed cube network, and then to connect the MIS nodes to form a CDS. The priority of an induced tree is determined according to a new parameter, the degree of the node in the square of a graph. This paper presents the proof that the ITCC generates a CDS with a lower approximation ratio. Furthermore, it is proved that the cardinality of the induced trees is a Fibonacci sequence, and an upper bound to the number of the dominating set is established. The simulations show that the algorithm provides the smallest CDS size compared with some other traditional algorithms.

4

An efficient connected dominating set algorithm in WSNs based on the induced tree of the crossed cube

63%

Zhang J. , Xu L. , Zhou S. M. , Wu W. , Ye X.

International Journal of Applied Mathematics and Computer Science

|

2015

|

tom Vol. 25, no. 2

295--309

EN

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of the crossed cube (ITCC) is presented. The ITCC is to find a maximal independent set (MIS), which is based on building an induced tree of the crossed cube network, and then to connect the MIS nodes to form a CDS. The priority of an induced tree is determined according to a new parameter, the degree of the node in the square of a graph. This paper presents the proof that the ITCC generates a CDS with a lower approximation ratio. Furthermore, it is proved that the cardinality of the induced trees is a Fibonacci sequence, and an upper bound to the number of the dominating set is established. The simulations show that the algorithm provides the smallest CDS size compared with some other traditional algorithms.