On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
复制标题
DOI：
10.1007/s00453-012-9689-4
复制
发表时间：
2011-08
期刊：
影响因子：
1.1
通讯作者：
Kei Uchizawa;T. Aoki;Takehiro Ito;Akira Suzuki;Xiaoping Zhou
中科院分区：
文献类型：
--
作者：
Kei Uchizawa;T. Aoki;Takehiro Ito;Akira Suzuki;Xiaoping Zhou
对于一个图G=(V，E)和一个颜色集合，令F：E→CBE G的一种边着色，其中两条相邻的边可能具有相同的颜色。然后，如果图G的每两个顶点都有一条所有边都被赋予不同颜色的路径，则该图是彩虹连通的。Chakraborty等人。定义了确定由给定的边着色所着色的图是否为彩虹连通的问题。Chen等人介绍了该问题的顶点着色形式，并在本文中介绍了全着色形式。我们解决了关于图直径的所有三个问题的精确计算复杂性，并针对某些图类：仙人掌图、外平面图和串-平行图刻画了这些问题。然后，我们给出了用颜色个数Inc.进行参数化时一般图上这三个问题的FPT算法；我们的FPT算法表明，对于任何有n个顶点的图，如果|C|=O(Logn)，这三个问题都可以在多项式时间内得到解决。
For a graphG=(V,E) and a color setC, letf:E→Cbe an edge-coloring ofGin which two adjacent edges may have the same color. Then, the graphGedge-colored byfis rainbow connected if every two vertices ofGhave a path in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems with regards to graph diameters, and also characterize these with regards to certain graph classes: cacti, outer planer and series-parallel graphs. We then give FPT algorithms for the three problems on general graphs when parameterized by the number of colors inC; our FPT algorithms imply that all the three problems can be solved in polynomial time for any graph withnvertices if |C|=O(logn).