Efficient Algorithm for Dominatig Set In Graph Theory Based on Fundamental Cut-Set

Furkan Öztemiz; Ali Karci

Makale detayları

Efficient Algorithm for Dominatig Set In Graph Theory Based on Fundamental Cut-Set

Yazarlar:

Furkan Öztemiz | Ali Karci

Yayıncı:

Gazi University

Ana Başlıklar:

Engineering

Dergi:

Gazi University Journal of Science Vol.37 Issue 2, pp.636-652

Belge Tipi:

Makale

Yayın Tarihi:

1/2024

Belge Dili:

İngilizce

Document ID (Org No.):

2001311647

pISSN:

2147-1762

Anahtar kelimeler:

Özet:

 Determining the minimum dominating set in connected graphs is one of the most difficult problems defined as NP-hard. In this problem, it is aimed to determine the important nodes that can influence all nodes via the minimum number of nodes on the graph. In this study, an efficient near-optimal algorithm showing a deterministic approach has been developed different from the approximation algorithms mentioned in the literature for discovering dominating set. The algorithm has On3 time complexity in determining the Dominating Set DS. At the same time, the algorithm is an original algorithm whose solution is not random by using a fundamental cut-set. The DS algorithm consists of 3 basic phases. In the first phase of the algorithm, the algorithm that constructs the special spanning tree Karci Max tree of the graph is developed. In the second phase, the algorithm that finds the fundamental cut sets using the Kmax spanning tree is developed. In the last phase, Karci centrality node values are calculated with fundamental cut set and by using these Karci centrality node values, an algorithm has been developed to identify DS nodes. As a result of these three phases, the dominance values of the nodes on the graph and the DS nodes are calculated. The detected Karci centrality node values give priority to the node selection for determining the DS. All phases of the developed DS and Efficient node algorithms were coded in R programming language and the results were examined by running on sample graphs.

 Determining the minimum dominating set in connected graphs is one of the most difficult problems defined as NP-hard. In this problem, it is aimed to determine the important nodes that can influence all nodes via the minimum number of nodes on the graph. In this study, an efficient near-optimal algorithm showing a deterministic approach has been developed different from the approximation algorithms mentioned in the literature for discovering dominating set. The algorithm has On3 time complexity in determining the Dominating Set DS. At the same time, the algorithm is an original algorithm whose solution is not random by using a fundamental cut-set. The DS algorithm consists of 3 basic phases. In the first phase of the algorithm, the algorithm that constructs the special spanning tree Karci Max tree of the graph is developed. In the second phase, the algorithm that finds the fundamental cut sets using the Kmax spanning tree is developed. In the last phase, Karci centrality node values are calculated with fundamental cut set and by using these Karci centrality node values, an algorithm has been developed to identify DS nodes. As a result of these three phases, the dominance values of the nodes on the graph and the DS nodes are calculated. The detected Karci centrality node values give priority to the node selection for determining the DS. All phases of the developed DS and Efficient node algorithms were coded in R programming language and the results were examined by running on sample graphs.

 Determining the minimum dominating set in connected graphs is one of the most difficult problems defined as NP-hard. In this problem, it is aimed to determine the important nodes that can influence all nodes via the minimum number of nodes on the graph. In this study, an efficient near-optimal algorithm showing a deterministic approach has been developed different from the approximation algorithms mentioned in the literature for discovering dominating set. The algorithm has On3 time complexity in determining the Dominating Set DS. At the same time, the algorithm is an original algorithm whose solution is not random by using a fundamental cut-set. The DS algorithm consists of 3 basic phases. In the first phase of the algorithm, the algorithm that constructs the special spanning tree Karci Max tree of the graph is developed. In the second phase, the algorithm that finds the fundamental cut sets using the Kmax spanning tree is developed. In the last phase, Karci centrality node values are calculated with fundamental cut set and by using these Karci centrality node values, an algorithm has been developed to identify DS nodes. As a result of these three phases, the dominance values of the nodes on the graph and the DS nodes are calculated. The detected Karci centrality node values give priority to the node selection for determining the DS. All phases of the developed DS and Efficient node algorithms were coded in R programming language and the results were examined by running on sample graphs.

 Determining the minimum dominating set in connected graphs is one of the most difficult problems defined as NP-hard. In this problem, it is aimed to determine the important nodes that can influence all nodes via the minimum number of nodes on the graph. In this study, an efficient near-optimal algorithm showing a deterministic approach has been developed different from the approximation algorithms mentioned in the literature for discovering dominating set. The algorithm has On3 time complexity in determining the Dominating Set DS. At the same time, the algorithm is an original algorithm whose solution is not random by using a fundamental cut-set. The DS algorithm consists of 3 basic phases. In the first phase of the algorithm, the algorithm that constructs the special spanning tree Karci Max tree of the graph is developed. In the second phase, the algorithm that finds the fundamental cut sets using the Kmax spanning tree is developed. In the last phase, Karci centrality node values are calculated with fundamental cut set and by using these Karci centrality node values, an algorithm has been developed to identify DS nodes. As a result of these three phases, the dominance values of the nodes on the graph and the DS nodes are calculated. The detected Karci centrality node values give priority to the node selection for determining the DS. All phases of the developed DS and Efficient node algorithms were coded in R programming language and the results were examined by running on sample graphs.

Makale detayları

Efficient Algorithm for Dominatig Set In Graph Theory Based on Fundamental Cut-Set

Yazarlar:

Furkan Öztemiz | Ali Karci

Yayıncı:

Gazi University

Ana Başlıklar:

Engineering

Dergi:

Gazi University Journal of Science Vol.37 Issue 2, pp.636-652

Belge Tipi:

Makale

Yayın Tarihi:

1/2024

Belge Dili:

İngilizce

Document ID (Org No.):

2001311647

pISSN:

2147-1762

Graph Theory

Dominating Set

Dominant Node

Karci Centrality

KMax TreeGraph Theory Dominating Set Dominant Node Karci Centrality KMax Tree

Graph Theory Dominating Set Dominant Node Karci Centrality KMax Tree

Dominating Set

Dominant Node

Karci Centrality

KMax Tree

Sayı

Makale detayları

Yazarlar: Furkan Öztemiz | Ali Karci

Yayıncı: Gazi University

Ana Başlıklar: Engineering

Dergi: Gazi University Journal of Science Vol.37 Issue 2, pp.636-652

Belge Tipi: Makale

Yayın Tarihi: 1/2024

Belge Dili: İngilizce

Document ID (Org No.): 2001311647

pISSN: 2147-1762

Sayı

Yazarlar:

Furkan Öztemiz | Ali Karci

Yayıncı:

Gazi University

Ana Başlıklar:

Engineering

Dergi:

Gazi University Journal of Science Vol.37 Issue 2, pp.636-652

Belge Tipi:

Makale

Yayın Tarihi:

1/2024

Belge Dili:

İngilizce

Document ID (Org No.):

2001311647

pISSN:

2147-1762