IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0267423
(2011-10-06)
|
등록번호 |
US-8724516
(2014-05-13)
|
발명자
/ 주소 |
- Young, Charles D.
- Amis, Alan D.
|
출원인 / 주소 |
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
1 인용 특허 :
12 |
초록
▼
The present disclosure is directed to a method for forming a connected dominating set (CDS) for a graph. The method may include directing each node of the graph to broadcast a dominating factor and neighboring node information; identifying a dominating set based on the dominating factor of each node
The present disclosure is directed to a method for forming a connected dominating set (CDS) for a graph. The method may include directing each node of the graph to broadcast a dominating factor and neighboring node information; identifying a dominating set based on the dominating factor of each node in comparison with dominating factors of neighboring nodes according to a dominating set rule definition; identifying a connecting set for connecting nodes according to a connecting set rule definition; and forming the CDS as a union of the dominating set and the connecting set.
대표청구항
▼
1. A method for forming a connected dominating set (CDS) for a graph, the method comprising: directing each node of the graph to broadcast a dominating factor and neighboring node information;identifying a dominating set, the dominating set being identified based on the dominating factor of each nod
1. A method for forming a connected dominating set (CDS) for a graph, the method comprising: directing each node of the graph to broadcast a dominating factor and neighboring node information;identifying a dominating set, the dominating set being identified based on the dominating factor of each node in comparison with dominating factors of neighboring nodes according to a dominating set rule definition;identifying a connecting set, the connecting set being identified for connecting nodes in the dominating set according to a connecting set rule definition; andforming the CDS as a union of the dominating set and the connecting set. 2. The method of claim 1, wherein a particular node i is identified as a member of the dominating set according to the dominating set rule definition: i∈DS⇒((∀j∈Ni(di>dj⋁(di+dj⋀i>j))⋁(∃j∈Ni∋∀k∈Nj(di>dk⋁(di=dk⋀i>k))) wherein: DS is the dominating set;i, j and k are nodes within the graph; anddi, dj and dk are the dominating factors of nodes i, j and k, respectively. 3. The method of claim 1, wherein a particular node i is identified as a member of the connecting set according to the connecting set rule definition: i∈CS′i∉DS(j∈DSk∈DS)(∃j,k∈NiDSNj∩DSNk≡φ)i∈CSi∈CS′∀n≠i∈CS′(di>dn(di=dni>n)) wherein: DS is the dominating set;CS is the connecting set;CS′ is the candidate set for CS;i, j, k and n are nodes within the graph;Ni represents a set of neighbors of node i;DSNj and DSNk represent sets of DS neighbors of nodes j and k, respectively; anddi and dn are the dominating factors of nodes i and n, respectively. 4. The method of claim 1, further comprising: applying an exception rule prior to identifying the connecting set, the exception rule is configured for excluding a particular node i according to the exception rule: i∉CS⇒(⫬∃l,m∈Ni⇒i∈CS)⋀((∃n∈CS∋n∈DSNj⋂DSNk)⋁(j∉DS⋀DSNi⋂DSNj≠ϕ)⋁(k∉DS⋀DSNi⋂DSNk≠ϕ)) wherein: DS is the dominating set;CS is the connecting set;i, j, k, l and m are nodes within the graph;Ni represents a set of neighbors of node i; andDSNj and DSNk represent sets of DS neighbors of nodes j and k, respectively. 5. The method of claim 1, further comprising: applying a not-CS rule prior to identifying the connecting set, the not-CS rule is configured for excluding a particular node i from the connecting set according to the not-CS rule: i∉CS∀j,k∈Ni(j∈Nkk∈Nj) wherein: CS is the connecting set;i, j and k are nodes within the graph;Ni, Nj and Nk represent sets of neighbors of nodes i, j and k, respectively. 6. The method of claim 1, wherein the dominating set rule definition is configured for providing fault tolerance for the dominating set, wherein a particular node i is identified as a member of the dominating set if: the dominating factor of said particular node i is at least the mth highest in comparison with dominating factors of the neighboring nodes of said particular node i; ora neighboring node j of said particular node i determines that the dominating factor of said particular node i is at least the mth highest in comparison with dominating factors of the neighboring nodes of node j. 7. The method of claim 1, wherein the dominating factor of each node is calculated according to a formula specified for a particular application. 8. The method of claim 7, wherein each node is further directed to broadcast a second dominating factor calculated according to a second formula specified for a second application, allowing formation of a second CDS to be executed in parallel with formation of the first mentioned CDS. 9. A method for forming a connected dominating set (CDS) for a graph, the method comprising: directing each node of the graph to broadcast a dominating factor and neighboring node information;identifying a dominating set for the graph according to the dominating set rule definition: i∈DS⇒((∀j∈Ni(di>dj⋁(di=dj⋀i>j))⋁(∃j∈Ni∋∀k∈Ni(di>dk⋁(di=dk⋀i>k)))wherein: DS is the dominating set;j and k are nodes within the graph; anddi, dj and dk are the dominating factors of nodes i, j and k, respectively;identifying a connecting set for connecting the nodes in the dominating set according to the connecting set rule definition: i∈CS′i∉DS(j∈DSk∈DS)(∃j,k∈NiDSNj∩DSNk≡φ)i∈CSi∈CS′∀n≠i∈CS′(di>dn(di=dni>n))wherein: DS is the dominating set;CS is the connecting set;CS′ is the candidate set for CS;i, j, k and n are nodes within the graph;Ni represents a set of neighbors of node i;DSNj and DSNk represent sets of DS neighbors of nodes j and k, respectively; anddi and dn are the dominating factors of nodes i and n, respectively; andforming the CDS as a union of the dominating set and the connecting set. 10. The method of claim 9, further comprising: applying a not-CS rule prior to identifying the connecting set, the not-CS rule is configured for excluding a particular node i from the connecting set according to the not-CS rule: i∉CS∀j,k∈Ni(j∈Nkk∈Nj) wherein: CS is the connecting set;i, j and k are nodes within the graph;Ni, Nj and Nk represent sets of neighbors of nodes i, j and k, respectively. 11. The method of claim 9, further comprising: applying an exception rule prior to identifying the connecting set, the exception rule is configured for excluding a particular node i according to the exception rule: i∉CS⇒(⫬∃l,m∈Ni⇒i∈CS)⋀((∃n∈CS∋n∈DSNj⋂DSNk)⋁(j∉DS⋀DSNi⋂DSNj≠ϕ)⋁(k∉DS⋀DSNi⋂DSNk≠ϕ)) wherein: DS is the dominating set;CS is the connecting set;i, j, k, l and m are nodes within the graph;Ni represents a set of neighbors of node i; andDSNj and DSNk represent sets of DS neighbors of nodes j and k, respectively. 12. The method of claim 9, wherein the dominating factor of each node is calculated according to a formula specified for a particular application. 13. The method of claim 12, wherein each node is further directed to broadcast a second dominating factor calculated according to a second formula specified for a second application, allowing formation of a second CDS to be executed in parallel with formation of the first mentioned CDS. 14. A method for forming a connected dominating set (CDS) for a graph, the method comprising: directing each node of the graph to broadcast a dominating factor and neighboring node information;identifying a dominating set, the dominating set being identified based on the dominating factor of each node in comparison with dominating factors of neighboring nodes according to a dominating set rule definition;identifying a connecting set for connecting the nodes in the dominating set, the identification of the connecting set further comprising: reducing a number of nodes to be processed during the identification of the connecting set according to at least one of a not-CS rule or an exception rule; andidentifying the connecting set according to a connecting set rule definition; andforming the CDS as a union of the dominating set and the connecting set. 15. The method of claim 14, wherein a particular node i is identified as a member of the dominating set according to the dominating set rule definition: i∈DS⇒((∀j∈Ni(di>dj⋁(di=dj⋀i>j))⋁(∃j∈Ni∋∀k∈Nj(di>dk⋁(di=dk⋀i>k))) wherein: DS is the dominating set;i, j and k are nodes within the graph; anddi, dj and dk are the dominating factors of nodes i, j and k, respectively. 16. The method of claim 14, wherein a particular node i is identified as a member of the connecting set according to the connecting set rule definition: i∈CS′i∉DS(j∈DSk∈DS)(∃j,k∈NiDSNj∩DSNk≡φ)i∈CSi∈CS′∀n≠i∈CS′(di>dn(di=dni>n)) wherein: DS is the dominating set;CS is the connecting set;CS′ is the candidate set for CS;i, j, k and n are nodes within the graph;Nj represents a set of neighbors of node i;DSNj and DSNk represent sets of DS neighbors of nodes j and k, respectively; anddi and dn are the dominating factors of nodes i and n, respectively. 17. The method of claim 14, wherein the not-CS rule is configured for excluding a particular node i from the connecting set according to the not-CS rule: i∉CS∀j,k∈Ni(j∈Nkk∈Nj) wherein: CS is the connecting set;i, j and k are nodes within the graph;Ni, Nj and Nk represent sets of neighbors of nodes i, j and k, respectively. 18. The method of claim 14, wherein the exception rule is configured for excluding a particular node i according to the exception rule: i∉CS⇒(⫬∃l,m∈Ni⇒i∈CS)⋀((∃n∈CS∋n∈DSNj⋂DSNk)⋁(j∉DS⋀DSNi⋂DSNj≠ϕ)⋁(k∉DS⋀DSNi⋂DSNk≠ϕ)) wherein: DS is the dominating set;CS is the connecting set;i, j, k, l and m are nodes within the graph;Nj represents a set of neighbors of node i; andDSNj and DSNk represent sets of DS neighbors of nodes j and k, respectively. 19. The method of claim 14, wherein each node is further directed to broadcast a second dominating factor, wherein the first mentioned dominating factor of each node is calculated according to a first formula specified for a first application and the second dominating factor of each node is calculated according to a second formula specified for a second application, allowing formation of a second CDS to be executed in parallel with formation of the first mentioned CDS. 20. The method of claim 14, wherein the dominating set rule definition is configured for providing fault tolerance, wherein a particular node i is identified as a member of the dominating set if: the dominating factor of said particular node i is at least the mth highest in comparison with dominating factors of the neighboring nodes of said particular node i; ora neighboring node j of said particular node i determines that the dominating factor of said particular node i is at least the mth highest in comparison with dominating factors of the neighboring nodes of node j.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.