Header menu link for other important links
X
Generation of simple, connected, non-isomorphic random graphs
M CHAKRABORTY, S CHOWDHURY,
Published in Springer Verlag
2020
Volume: 995
   
Pages: 69 - 77
Abstract
In graph theory, generation of random graphs finds a wide range of applications in different scheduling problems, approximation algorithms, problems involving modeling and simulation, different database applications, and obviously to test the performance of any algorithm. The algorithm, which has been devised in this paper, is mainly for the purpose of providing test bed for checking performance of other algorithms. It generates different non-isomorphic graph instances of a given order and having unique number of edges. The number of such instances possible for a graph of given order has also been subsequently formulated. Different such graph instances of different orders, generated in a uniform computing environment, and the computing time required for such generations have also been included in this paper. The simplicity and efficiency of the algorithm, subsequently proved in the paper, give us a new insight in the area of random graph generation and have called for further research scope in the domain. © 2020, Springer Nature Singapore Pte Ltd.
About the journal
JournalData powered by TypesetAdvances in Intelligent Systems and Computing
PublisherData powered by TypesetSpringer Verlag
ISSN2194-5357
Open AccessNo