Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Algorithms for Computing Domination and Total Domination Numbers of RNPCG

Authors: null Renuka Lakshmi Avvari;

Algorithms for Computing Domination and Total Domination Numbers of RNPCG

Abstract

Introduction: This paper presents an efficient algorithmic framework for computing the domination number (γ) and total domination number (γt) of graphs, with a focus on applications in collaboration networks. Using a greedy approach combined with minimality verification, the algorithm identifies dominating and total dominating sets that optimize connectivity within the graph structure. Objectives: To design and implement algorithms for computing the domination number of RNPCGs, focusing on both time complexity and practical efficiency. Methods: The methodology is demonstrated on the Rolf Nevanlinna Prize Collaboration Graph (RNPCG), showcasing its ability to handle complex, real-world datasets. Results reveal key insights into the connectivity and influence metrics of prominent academic networks, with implications for optimizing resource dissemination in such systems. The proposed algorithm balances computational efficiency with accuracy, offering a robust tool for graph-theoretic analysis in both theoretical and applied contexts Results: A detailed computational complexity analysis was conducted for both the domination number and total domination number algorithms. It was found that the proposed solutions offer polynomial-time complexity for graphs of moderate size, making them practical for typical use cases. However, the complexity does increase with the size of the graph, especially as the randomness in RNPCGs increases.The algorithms were also compared with exact brute-force solutions for small graphs, showing that our approach provides a significant reduction in computation time while maintaining accuracy. Conclusions: In this study, we developed an efficient algorithm for computing the domination number (γ) and total domination number (γt) in graphs, with a focus on its application to the Rolf Nevanlinna Prize Collaboration Graph (RNPCG). By leveraging a greedy approach and minimality verification, the algorithm effectively identified dominating and total dominating sets, providing insights into the connectivity and structural properties of the RNPCG. The analysis revealed the influence and connectivity of key vertices, illustrating the practical utility of domination metrics in understanding complex collaboration networks. The results emphasize the significance of domination parameters in optimizing resource dissemination and maintaining connectivity within academic or similar real-world networks.

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!