Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.17223 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914771776831488 |
|---|---|
| author | Watel, Dimitri Weisser, Marc-Antoine Barth, Dominique Aboulfath, Ylène Mautor, Thierry |
| author_facet | Watel, Dimitri Weisser, Marc-Antoine Barth, Dominique Aboulfath, Ylène Mautor, Thierry |
| contents | We address a specific case of the matroid intersection problem: given a set of graphs sharing the same set of vertices, select a minimum cycle basis for each graph to maximize the size of their intersection. We provide a comprehensive complexity analysis of this problem, which finds applications in chemoinformatics. We establish a complete partition of subcases based on intrinsic parameters: the number of graphs, the maximum degree of the graphs, and the size of the longest cycle in the minimum cycle bases. Additionally, we present results concerning the approximability and parameterized complexity of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17223 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximizing Minimum Cycle Bases Intersection Watel, Dimitri Weisser, Marc-Antoine Barth, Dominique Aboulfath, Ylène Mautor, Thierry Computational Complexity We address a specific case of the matroid intersection problem: given a set of graphs sharing the same set of vertices, select a minimum cycle basis for each graph to maximize the size of their intersection. We provide a comprehensive complexity analysis of this problem, which finds applications in chemoinformatics. We establish a complete partition of subcases based on intrinsic parameters: the number of graphs, the maximum degree of the graphs, and the size of the longest cycle in the minimum cycle bases. Additionally, we present results concerning the approximability and parameterized complexity of the problem. |
| title | Maximizing Minimum Cycle Bases Intersection |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.17223 |