Search

Granular computing (GrC) is a methodology for reducing the complexity of problem solving and includes two basic aspects: granulation and granular-based computing. Strongly connected components (SCCs) are a significant subgraph structure in digraphs. In this paper, two new granulation strategies were devised to improve the efficiency of computing SCCs. Firstly, four SCC correlations between the vertices were found, which can be divided into two classes. Secondly, two granulation strategies were designed based on correlations between two classes of SCCs. Thirdly, according to the characteristics of the granulation results, the parallelization of computing SCCs was realized. Finally, a parallel algorithm based on granulation strategy for computing SCCs of simple digraphs named GPSCC was proposed. Experimental results show that GPSCC performs with higher computational efficiency than algorithms. [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

The problem of the interferometric phase unwrapping in radar remote sensing of Earth systems is considered. Such interferograms are widely used in the problems of creating and updating maps of the relief of the Earth's surface in geodesy, cartography, environmental monitoring, geological, hydrological and glaciological studies, and for monitoring transport communications. Modern radar systems have ultra-high spatial resolution and a wide band, which leads to the need to unwrap large interferograms from several tens of millions of elements. The implementation of calculations by these methods requires a processing time of several days. In this paper, an effective method for equalizing the inverse vortex field for phase unwrapping is proposed, which allows solving a problem with quasi-linear computational complexity depending on the interferogram size and the number of singular points on it. To implement the method, a parallel algorithm for solving the problem on a multi-core processor using OpenMP technology was developed. Numerical experiments on radar data models were carried out to investigate the effectiveness of the algorithm depending on the size of the source data, the density of singular points and the number of processor cores. [ABSTRACT FROM AUTHOR]