Algorithmic methods of finite discrete structures. Graph clique problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909370524106752 |
|---|---|
| author | Kurapov, Sergey Davidovsky, Maxim |
| author_facet | Kurapov, Sergey Davidovsky, Maxim |
| contents | The monography presents a new algorithm for finding the clique of maximal length in a nonseparable graph. The algorithm is based on the properties of the representation of a clique as a subset of the set of cycles with a length of three, the ring sum of which is an empty set. As a result of selecting the cycles of the length of three, two vectors are formed: the vector of cycles passing through the edges and the vector of cycles passing through the vertices. The numerical values of the components of these vectors determine the weights of the vertices and edges. The iterative process of constructing the set of vectors of cycles passing through the edges allows identifying the main vector of cycles passing through the edges. In turn, the construction of the main vector allows finding the clicks of the graph. The computational complexity of the presented algorithm is analyzed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22039 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Algorithmic methods of finite discrete structures. Graph clique problem Kurapov, Sergey Davidovsky, Maxim Discrete Mathematics Computational Complexity Combinatorics The monography presents a new algorithm for finding the clique of maximal length in a nonseparable graph. The algorithm is based on the properties of the representation of a clique as a subset of the set of cycles with a length of three, the ring sum of which is an empty set. As a result of selecting the cycles of the length of three, two vectors are formed: the vector of cycles passing through the edges and the vector of cycles passing through the vertices. The numerical values of the components of these vectors determine the weights of the vertices and edges. The iterative process of constructing the set of vectors of cycles passing through the edges allows identifying the main vector of cycles passing through the edges. In turn, the construction of the main vector allows finding the clicks of the graph. The computational complexity of the presented algorithm is analyzed. |
| title | Algorithmic methods of finite discrete structures. Graph clique problem |
| topic | Discrete Mathematics Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2410.22039 |