کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418567 681688 2015 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of the flow coloring problem
ترجمه فارسی عنوان
در پیچیدگی مشکل رنگ آمیزی جریان
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Motivated by bandwidth allocation under interference constraints in radio networks, we define and investigate an optimization problem that combines the classical flow and edge coloring problems in graphs. Let G=(V,E)G=(V,E) be a graph with a demand function b:V→Z+b:V→Z+ and a gateway  g∈V∖Vsg∈V∖Vs, where Vs={v∈V:b(v)>0}Vs={v∈V:b(v)>0} is the set of source nodes  . A flow ϕuϕu of a source node uu is a multiset of b(u)b(u) paths in GG from uu to gg. A flow ϕϕ on GG is a set with one flow for each source node. Every flow ϕϕ defines a multigraph GϕGϕ with vertex set VV and all edges in the paths in ϕϕ. A distance-  ddedge coloring   of a flow ϕϕ is an edge coloring of GϕGϕ such that two edges with the same color are at distance at least dd in GG. The distance-  ddflow coloring problem   (FCPdFCPd) is the problem of obtaining a flow ϕϕ on GG with a distance-dd edge coloring where the number of used colors is minimum. For any fixed d≥3d≥3, we prove that FCPdFCPd is NP-hard even on a bipartite graph with just one source node. For d=2d=2, we also prove NP-hardness on a bipartite graph with multiples sources. For d=1d=1, we show that the problem is polynomial in 3-connected graphs and bipartite graphs. Finally, we show that a list version of the problem is inapproximable in polynomial time by a factor of O(logn)O(logn) even on nn-vertex paths, for any d≥1d≥1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 197, 31 December 2015, Pages 75–92
نویسندگان
, , , ,