61. Color-avoiding connected spanning subgraphs with minimum number of edges
Invited abstract in session TC-3: Approximation algorithms for graph problems, stream Approximation algorithms.
Thursday, 12:00 - 13:30Room: C 104
Authors (first author is the speaker)
| 1. | Kitti Varga
|
| HUN-REN–ELTE Egerváry Research Group |
Abstract
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 talk, we investigate the problem of determining the maximum number of edges that can be removed from either an edge- or a vertex-colored, color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, and 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.
This is a joint work with József Pintér.
Keywords
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers