Generalized rainbow connectivity of graphs

作者：Uchizawa Kei^*; Aoki Takanori; Ito Takehiro; Zhou Xiao

来源：Theoretical Computer Science, 2014, 555: 35-42.

DOI：10.1016/j.tcs.2014.01.007

• Cactus
• Fixed parameter tractability
• Graph algorithm
• Rainbow connectivity
• Tree

Let C = {c(1), c(2), ..., c(k)} be a set of k colors, and let (l) over right arrow = (l(1), l(2), ..., l(k)) be a k-tuple of nonnegative integers l(1), l(2), ..., l(k). For a graph G = (V, E), let f : E -%26gt; C be an edgecoloringof G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is (l) over right arrow -rainbow connected if every two vertices of G have a path Pconnecting them such that the number of edges on P that are colored with c(j) is at most for each index j epsilon {1, 2, ..., k}. Given a k-tuple (l) over right arrow and an edge-colored graph, we study the problem of determining whether the edge-colored graph is (l) over right arrow -rainbow connected. In this paper, we first study the computational complexity of the problem with regard to certain graph classes: the problem is NP-complete even for cacti, while is solvable in polynomial time for trees. We then give an FPT algorithm for general graphs when parameterized by both k and l(max) = max{l(j) vertical bar 1 %26lt;= j %26lt;= k}.

• 出版日期2014-10-23