Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor
The relevance of the research is caused by the unsolved problem of searching for the complete graph invariant and polynomial algorithm for its computing. The aim of the research is in determining the complete invariant of an ordinary graph on the basis of integral descriptor of abstract structure an...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Tomsk Polytechnic University
2019-05-01
|
| Series: | Известия Томского политехнического университета: Инжиниринг георесурсов |
| Subjects: | |
| Online Access: | http://izvestiya-tpu.ru/archive/article/view/1203 |
| _version_ | 1797812532980744192 |
|---|---|
| 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 unsolved problem of searching for the complete graph invariant and polynomial algorithm for its computing. The aim of the research is in determining the complete invariant of an ordinary graph on the basis of integral descriptor of abstract structure and in developing the efficient algorithm for computing the complete invariant. The techniques of the research are based on the graph theory and the theory of structural differences code integration in abstract graph structures. The authors have proposed the algorithm for solving one of the most complex problems of graph theory. It is the computation of complete graph invariant. The algorithm is based on the methods of free and dependent integration of structural differences codes in a graph; it is characterized by simplicity, efficiency and it has polynomial estimation of the limiting amount of computation. The complete invariant is represented in the form of a vector of integral descriptor for graph abstract structure vertices and contains information for forming isomorphism substitution. Using Java the GraphISD software was developed implementing the proposed algorithm. The paper introduces the examples of computing the complete invariants at free and dependent integration. |
| first_indexed | 2024-03-13T07:38:56Z |
| format | Article |
| id | doaj.art-b1a55f21a6094de2a230db41a45995a9 |
| institution | Directory Open Access Journal |
| issn | 2500-1019 2413-1830 |
| language | Russian |
| last_indexed | 2024-03-13T07:38:56Z |
| publishDate | 2019-05-01 |
| publisher | Tomsk Polytechnic University |
| record_format | Article |
| series | Известия Томского политехнического университета: Инжиниринг георесурсов |
| spelling | doaj.art-b1a55f21a6094de2a230db41a45995a92023-06-03T21:07:29ZrusTomsk Polytechnic UniversityИзвестия Томского политехнического университета: Инжиниринг георесурсов2500-10192413-18302019-05-013235Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptorV. K. PogrebnoyA. V. PogrebnoyThe relevance of the research is caused by the unsolved problem of searching for the complete graph invariant and polynomial algorithm for its computing. The aim of the research is in determining the complete invariant of an ordinary graph on the basis of integral descriptor of abstract structure and in developing the efficient algorithm for computing the complete invariant. The techniques of the research are based on the graph theory and the theory of structural differences code integration in abstract graph structures. The authors have proposed the algorithm for solving one of the most complex problems of graph theory. It is the computation of complete graph invariant. The algorithm is based on the methods of free and dependent integration of structural differences codes in a graph; it is characterized by simplicity, efficiency and it has polynomial estimation of the limiting amount of computation. The complete invariant is represented in the form of a vector of integral descriptor for graph abstract structure vertices and contains information for forming isomorphism substitution. Using Java the GraphISD software was developed implementing the proposed algorithm. The paper introduces the examples of computing the complete invariants at free and dependent integration.http://izvestiya-tpu.ru/archive/article/view/1203complete graph invariantgraph isomorphismintegral structure descriptorabstract graph structurecode integration areapolynomial algorithm |
| spellingShingle | V. K. Pogrebnoy A. V. Pogrebnoy Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor Известия Томского политехнического университета: Инжиниринг георесурсов complete graph invariant graph isomorphism integral structure descriptor abstract graph structure code integration area polynomial algorithm |
| title | Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor |
| title_full | Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor |
| title_fullStr | Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor |
| title_full_unstemmed | Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor |
| title_short | Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor |
| title_sort | polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor |
| topic | complete graph invariant graph isomorphism integral structure descriptor abstract graph structure code integration area polynomial algorithm |
| url | http://izvestiya-tpu.ru/archive/article/view/1203 |
| work_keys_str_mv | AT vkpogrebnoy polynomialalgorithmofcomputingcompletegraphinvariantonthebasisofintegralstructuredescriptor AT avpogrebnoy polynomialalgorithmofcomputingcompletegraphinvariantonthebasisofintegralstructuredescriptor |