Back to Search
Start Over
Color-avoiding connected spanning subgraphs with minimum number of edges.
- Source :
-
Discrete Applied Mathematics . May2024, Vol. 349, p25-43. 19p. - Publication Year :
- 2024
-
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 article, 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 349
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 176247650
- Full Text :
- https://doi.org/10.1016/j.dam.2024.01.044