Color-avoiding connected spanning subgraphs with minimum number of edges
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910308267720704 |
|---|---|
| author | Pintér, József Varga, Kitti |
| author_facet | Pintér, József Varga, Kitti |
| contents | We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from a color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, then we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_11035 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Color-avoiding connected spanning subgraphs with minimum number of edges Pintér, József Varga, Kitti Combinatorics We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from a color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, then we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids. |
| title | Color-avoiding connected spanning subgraphs with minimum number of edges |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2302.11035 |