Algorithmic approach to find -consistency in Common-Edge signed graph
Anshu Sethi1, Deepa Sinha2, Obaidullah Wardak2
1The North Cap University, India.
Methodsx
|August 9, 2022
Summary
This study introduces an algorithm to determine if a signed graph is common-edge consistent. The research also analyzes the complexity of this consistency detection algorithm.
Area of Science:
- Graph Theory
- Discrete Mathematics
- Computer Science
Background:
- Introduces the concept of a common-edge signed graph derived from an initial signed graph.
- Defines a marked signed graph and the condition for a signed graph to be common-edge consistent.
Purpose of the Study:
- To develop and present an algorithm for detecting common-edge consistency in signed graphs.
- To determine the computational complexity of the proposed algorithm.
Main Methods:
- An algorithm is designed to systematically check for common-edge consistency.
- The algorithm's performance is analyzed to establish its time and space complexity.
Main Results:
- A novel algorithm for detecting common-edge consistency in signed graphs is presented.
- The complexity of the developed algorithm is determined, providing insights into its efficiency.
Conclusions:
- The study provides a computational method for assessing common-edge consistency in signed graphs.
- The complexity analysis offers a quantitative understanding of the algorithm's resource requirements.
More Related Videos
Related Concept Videos
01:10Vector Algebra: Graphical Method
13.1K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
13.1K
01:12Theorems of Pappus and Guldinus: Problem Solving
788
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
788
01:17Sign Test for Matched Pairs
202
The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in...
To conduct the sign test, we first calculate the differences in...
202
02:33Lattice Centering and Coordination Number
9.8K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
Types of Unit Cells
Imagine taking a large number of identical...
9.8K
01:19Routh-Hurwitz Criterion II
384
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
384
01:15Routh-Hurwitz Criterion I
323
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
323