Polynomiality of method for computing graph structure integral descriptor
The relevance of the research is caused by the necessity of developing the efficient method of invariant description and analysis of abstract structures of graph models. The aim of the research is to substantiate the polinomiality of the method for computing the integral descriptor of graph abstract...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Tomsk Polytechnic University
2019-05-01
|
| Series: | Известия Томского политехнического университета: Инжиниринг георесурсов |
| Subjects: | |
| Online Access: | http://izvestiya.tpu.ru/archive/article/view/1202 |
| _version_ | 1797813219490791424 |
|---|---|
| author | V. K. Pogrebnoy A. V. Pogrebnoy |
| author_facet | V. K. Pogrebnoy A. V. Pogrebnoy |
| author_sort | V. K. Pogrebnoy |
| collection | DOAJ |
| description | The relevance of the research is caused by the necessity of developing the efficient method of invariant description and analysis of abstract structures of graph models. The aim of the research is to substantiate the polinomiality of the method for computing the integral descriptor of graph abstract structure proposed by the authors. The research techniques are based on application of machinery of graph theory and methods of free and dependent integration of codes of graph structural differences. The authors have introduced the notion of stable group of vertices in graph and stated the conditions of occurrence and existence of such groups at integration of structural differences codes when computing the integral structure descriptor. A number of features which disclose the appropriateness of application of the main rules of the integral structure descriptor and its polinomiality was determined for stable groups. It was ascertained on the basis of the defined features that the conditions for stable group existing are conditioned by hard limits; the vertices of different stable groups can not generate new stable groups. The authors have also defined the factor of full isolation of stable groups that predetermined considerably the efficiency of algorithm for computing the full graph structure descriptor. Polinomiality of the technique is demonstrated for the most complex case when graphs are homogeneous and contain stable groups. The authors developed Java GraphISD software for the experimental investigations of integral structure descriptor technique and introduced the results of its operation. |
| first_indexed | 2024-03-13T07:50:05Z |
| format | Article |
| id | doaj.art-774e703f941141fd85e94abe4d61221b |
| institution | Directory Open Access Journal |
| issn | 2500-1019 2413-1830 |
| language | Russian |
| last_indexed | 2024-03-13T07:50:05Z |
| publishDate | 2019-05-01 |
| publisher | Tomsk Polytechnic University |
| record_format | Article |
| series | Известия Томского политехнического университета: Инжиниринг георесурсов |
| spelling | doaj.art-774e703f941141fd85e94abe4d61221b2023-06-02T21:07:21ZrusTomsk Polytechnic UniversityИзвестия Томского политехнического университета: Инжиниринг георесурсов2500-10192413-18302019-05-013235Polynomiality of method for computing graph structure integral descriptorV. K. PogrebnoyA. V. PogrebnoyThe relevance of the research is caused by the necessity of developing the efficient method of invariant description and analysis of abstract structures of graph models. The aim of the research is to substantiate the polinomiality of the method for computing the integral descriptor of graph abstract structure proposed by the authors. The research techniques are based on application of machinery of graph theory and methods of free and dependent integration of codes of graph structural differences. The authors have introduced the notion of stable group of vertices in graph and stated the conditions of occurrence and existence of such groups at integration of structural differences codes when computing the integral structure descriptor. A number of features which disclose the appropriateness of application of the main rules of the integral structure descriptor and its polinomiality was determined for stable groups. It was ascertained on the basis of the defined features that the conditions for stable group existing are conditioned by hard limits; the vertices of different stable groups can not generate new stable groups. The authors have also defined the factor of full isolation of stable groups that predetermined considerably the efficiency of algorithm for computing the full graph structure descriptor. Polinomiality of the technique is demonstrated for the most complex case when graphs are homogeneous and contain stable groups. The authors developed Java GraphISD software for the experimental investigations of integral structure descriptor technique and introduced the results of its operation.http://izvestiya.tpu.ru/archive/article/view/1202integral structure descriptorgraph isomorphismabstract graph structurestable group of verticescode integration areaalgorithm polynomiality |
| spellingShingle | V. K. Pogrebnoy A. V. Pogrebnoy Polynomiality of method for computing graph structure integral descriptor Известия Томского политехнического университета: Инжиниринг георесурсов integral structure descriptor graph isomorphism abstract graph structure stable group of vertices code integration area algorithm polynomiality |
| title | Polynomiality of method for computing graph structure integral descriptor |
| title_full | Polynomiality of method for computing graph structure integral descriptor |
| title_fullStr | Polynomiality of method for computing graph structure integral descriptor |
| title_full_unstemmed | Polynomiality of method for computing graph structure integral descriptor |
| title_short | Polynomiality of method for computing graph structure integral descriptor |
| title_sort | polynomiality of method for computing graph structure integral descriptor |
| topic | integral structure descriptor graph isomorphism abstract graph structure stable group of vertices code integration area algorithm polynomiality |
| url | http://izvestiya.tpu.ru/archive/article/view/1202 |
| work_keys_str_mv | AT vkpogrebnoy polynomialityofmethodforcomputinggraphstructureintegraldescriptor AT avpogrebnoy polynomialityofmethodforcomputinggraphstructureintegraldescriptor |