On the matching arrangement of a graph, improper weight function problem and its application
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913660595601408 |
|---|---|
| author | Bolotnikov, Aleksey Irmatov, Anwar |
| author_facet | Bolotnikov, Aleksey Irmatov, Anwar |
| contents | This article presents examples of an application of the finite field method for the computation of the characteristic polynomial of the matching arrangement of a graph. Weight functions on edges of a graph with weights from a finite field are divided into proper and improper functions in connection with proper colorings of vertices of the matching polytope of a graph. An improper weight function problem is introduced, a proof of its NP-completeness is presented, and a knapsack-like public key cryptosystem is constructed based on the improper weight function problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19351 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the matching arrangement of a graph, improper weight function problem and its application Bolotnikov, Aleksey Irmatov, Anwar Combinatorics Cryptography and Security Discrete Mathematics This article presents examples of an application of the finite field method for the computation of the characteristic polynomial of the matching arrangement of a graph. Weight functions on edges of a graph with weights from a finite field are divided into proper and improper functions in connection with proper colorings of vertices of the matching polytope of a graph. An improper weight function problem is introduced, a proof of its NP-completeness is presented, and a knapsack-like public key cryptosystem is constructed based on the improper weight function problem. |
| title | On the matching arrangement of a graph, improper weight function problem and its application |
| topic | Combinatorics Cryptography and Security Discrete Mathematics |
| url | https://arxiv.org/abs/2411.19351 |