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.

RAJAT PAL

Computer Science and Engineering

M CHAKRABORTY

S CHOWDHURY

University of Calcutta (informally known as Calcutta University or CU) is a collegiate public state university located in Kolkata, West Bengal, India.&nbsp;Within India it is recognized as a &quot;Five-Star University&quot; and accredited &quot;A&quot; Grade by National Assessment and Accreditation Council.

&nbsp;

The University of Calcutta has secured the Fifth position among the Universities of India in the prestigious &quot;Indian University Ranking 2019&quot; list, released by the NIRF of the Ministry of Human Resource Development, Government of India.

&nbsp;

It was established on 24 January 1857, and was one of the first institutions in Asia to be established as a multidisciplinary and Western-style university. Its alumni and faculty include several heads of state, heads of government, social reformers, prominent artists, only academy award winner and Dirac medal winner in India, many Fellows of the Royal Society and five Nobel laureates as of 2019 which is highest in South Asia.

University Of Calcutta

Generation of Simple, Connected, Non-isomorphic Random Graphs

Advances in Intelligent Systems and Computing

Channel routing and crosstalk minimization are important issues while we talk about high-performance circuits for VLSI physical design automation. Interconnection among the net terminals satisfying constraints in an intelligent way is a necessity to realize a circuit in a minimum possible area, as this is a primary requirement to reduce cost as well as to increase yield. In this paper, along with area minimization, the performance of the computed circuits has also been enhanced by computing routing solutions with a specified amount of bottleneck crosstalk in two-layer channel routing. Usually, crosstalk is measured by the amount of overlapping of a pair of nets assigned to adjacent tracks. The crosstalk minimization problem in the reserved two-layer Manhattan channel routing model is NP-hard. Thus, in this paper, heuristic algorithms have been devised to optimize bottleneck crosstalk in order to augment circuit performance in two-layer channel routing. Experimental results obtained are highly encouraging. © 2020, Springer Nature Singapore Pte Ltd.

Lecture Notes in Electrical Engineering

Algorithms for minimizing bottleneck crosstalk in two-layer channel routing

i* models are inherently sequence agnostic. This makes the process of cross-checking i* models against temporal properties quite impossible. There is an immediate industrial need to bridge the gap between such a sequence agnostic model and a standardized model verifier so that model checking can be performed in the requirement analysis phase itself. In this paper, we first spell out the Naive Algorithm that generates all possible finite state models corresponding to a given i* model. The growth of the finite state model space can be mapped to the problem of finding the number of possible paths between the Least Upper Bound (LUB) and the Greatest Lower Bound (GLB) of a k-dimensional hypercube lattice structure. The mathematics for doing a quantitative analysis of the space growth has also been presented. The Naive Algorithm has its main drawback in the hyperexponential growth of the model space. The Semantic Implosion Algorithm is proposed as a solution to the hyperexponential problem. This algorithm exploits the temporal information embedded within the i* model of an enterprise to reduce the rate of growth of the finite state model space. A comparative quantitative analysis between the two approaches concludes the superiority of the Semantic Implosion Algorithm. © 2016

Fulltext

Journal of Systems and Software

Extracting finite state models from i* models

Goal model like i∗ are inherently sequence agnostic whereas standard model checkers like SPIN or NuSMV accept extended finite state models which represent an ordering of state transitions that can occur within a system. These two notions are mutually conflicting and, thus, we cannot check temporal properties (like compliance rules), described using temporal languages (like Linear Temporal Logic (LTL), or Computational Tree Logic (CTL)), on goal models by feeding them as input to a standard model checker. The i∗ToNuSMV tool aims to bridge this gap such that the compliance of i∗ models towards temporal constraints can be verified in the early requirements phase of software development itself. © 2016 IEEE.

Proceedings - 2016 IEEE 24th International Requirements Engineering Conference, RE 2016

Iâˆ—ToNuSMV: A Prototype for Enabling Model Checking of iâˆ— Models

i∗ is a goal oriented requirements engineering tool that can model varied requirements for solutions being developed by an enterprise. Different stakeholders within an enterprise may use partial or even completely non-intersecting vocabulary sets. This would lead to developing multiple i∗ models having independent ontologies. Collectively, these i∗ models define a requirements refinement hierarchy where different tiers of the hierarchy capture different levels of detail. In order to integrate such a distributed ontology, we require an appropriate mapping or correlate definitions between different ontologies at multiple levels. This paper tries to identify different types of bridging correlations that allow an integration of multi-ontological i∗ refinement hierarchies. We use these correlations to demonstrate how relative completeness can be established between adjacent tiers of the hierarchy. Varying degrees of relative completeness have also been identified and their fulfillment criteria have been summarized as theorems. A University Admissions System has been used as a case study to illustrate heuristics for achieving greater relative completeness. © 2015 IEEE.

5th International Model-Driven Requirements Engineering Workshop, MoDRE 2015 - Proceedings

Using iâˆ— model towards ontology integration and completeness checking in enterprise systems requirement hierarchy

Crosstalk minimization is one of the most important high performance aspects in interconnecting VLSI circuits. With advancement of fabrication technology, devices and interconnecting wires are placed in closer proximity and circuits operate at higher frequencies. This results in crosstalk between wire segments. Crosstalk minimization problem for the reserved two-layer Manhattan channel routing is NP-hard, even if the channel instances are free from any vertical constraint (simplest channel instances). In this paper we have developed heuristic algorithms for computing reduced crosstalk two-layer channel routing solutions for simplest as well as general channel instances. In general, the results obtained are highly encouraging. ©2007 IEEE.

Journal	Data powered by TypesetAdvances in Intelligent Systems and Computing
Publisher	Data powered by TypesetSpringer Verlag
ISSN	2194-5357
Open Access	No