TY - JOUR

T1 - Generalized rainbow connectivity of graphs

AU - Uchizawa, Kei

AU - Aoki, Takanori

AU - Ito, Takehiro

AU - Zhou, Xiao

N1 - Publisher Copyright:
© 2014 Elsevier B.V.

PY - 2014

Y1 - 2014

N2 - Let C={c1, c2,..., ck} be a set of k colors, and let ℓ→=(ℓ1,ℓ2,...,ℓk) be a k-tuple of nonnegative integers ℓ1, ℓ2,..., ℓk. For a graph G=(V, E), let f:E→C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is ℓ→-rainbow connected if every two vertices of G have a path P connecting them such that the number of edges on P that are colored with cj is at most ℓj for each index j∈{1, 2,..., k}. Given a k-tuple ℓ→ and an edge-colored graph, we study the problem of determining whether the edge-colored graph is ℓ→-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 ℓmax=max {ℓj|1≤j≤k}.

AB - Let C={c1, c2,..., ck} be a set of k colors, and let ℓ→=(ℓ1,ℓ2,...,ℓk) be a k-tuple of nonnegative integers ℓ1, ℓ2,..., ℓk. For a graph G=(V, E), let f:E→C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is ℓ→-rainbow connected if every two vertices of G have a path P connecting them such that the number of edges on P that are colored with cj is at most ℓj for each index j∈{1, 2,..., k}. Given a k-tuple ℓ→ and an edge-colored graph, we study the problem of determining whether the edge-colored graph is ℓ→-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 ℓmax=max {ℓj|1≤j≤k}.

KW - Cactus

KW - Fixed parameter tractability

KW - Graph algorithm

KW - Rainbow connectivity

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=84926277152&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84926277152&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2014.01.007

DO - 10.1016/j.tcs.2014.01.007

M3 - Article

AN - SCOPUS:84926277152

SN - 0304-3975

VL - 555

SP - 35

EP - 42

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -